Codeforces 575F (最短路)

2019-07-26 by fffasttime·0评论

题意：n个点m条边的图，求两两无序点对中最短路第k小的长度。n,m<=2e5，k<=400。注意，自环不算最短路，(a,b), (b,a)只算一条。

尝试使用最麻烦的方法过题，写了一个map魔改的dijk卡内存卡过去。。。其实是个大水题，因为有用的边最多有400条，所以把最短的400条拿出来做个Floyd就好了。。。

```
#include <bits/stdc++.h>
```
```
using namespace std;
```
```
#define inc(i,n) for(int i=0;i<n;i++)
```
```
typedef long long ll;
```
```
 
```
```
struct Edge{
```
```
	int v; ll w;
```
```
	bool operator<(const Edge &t) const{
```
```
		return w==t.w?v<t.v:w<t.w;
```
```
	}
```
```
};
```
```
vector<Edge> ed[200010];
```
```
map<pair<int,int>,ll> dis;
```
```
set<pair<int,int>> vis;
```
```
struct Node{
```
```
	ll w;int fr, to;
```
```
	bool operator<(const Node &v)const{
```

		if (w==v.w) return fr==v.fr?to<v.to:fr<v.fr;

```
		return w>v.w;
```
```
	}
```
```
};
```
```
 
```
```
int main(){
```
```
	int n,m,k; cin>>n>>m>>k;
```
```
	inc(i,m){
```

		int u,v; ll w; scanf("%d%d%lld",&u,&v,&w);

```
		ed[u].push_back({v,w});
```
```
		ed[v].push_back({u,w});
```
```
	}
```
```
	priority_queue<Node> qu;
```

	for (int i=1;i<=n;i++) qu.push({0,i,i}),sort(ed[i].begin(),ed[i].end());

```
	k*=2;
```
```
	while (1){
```
```
		Node t=qu.top(); qu.pop();
```
```
		if (vis.count({t.fr,t.to})) continue;
```
```
		if (t.fr^t.to) k--;
```
```
		if (k==0){
```
```
			cout<<t.w<<'\n';
```
```
			exit(0);
```
```
		}
```
```
		vis.insert({t.fr,t.to});
```
```
		int u=t.to;
```
```
		ll w0=t.w;
```
```
		int cnt=0;
```
```
		for (auto &e:ed[u]){
```
```
			int v=e.v;
```

			if (!vis.count({t.fr,v}) && (!dis.count({t.fr,v}) || dis[{t.fr,v}]>w0+e.w)){

```
				dis[{t.fr,v}]=w0+e.w;
```
```
				qu.push({w0+e.w,t.fr,v});
```
```
			}
```
```
			cnt++; if(cnt==500) break;
```
```
		}
```
```
	}
```
```
	return 0;
```
```
}
```

发表评论取消回复