codeforces 1196F K-th Path 思维+floyd

http://codeforces.com/problemset/problem/1196/F
You are given a connected undirected weighted graph consisting of n vertices and m edges.

You need to print the k-th smallest shortest path in this graph (paths from the vertex to itself are not counted, paths from i to j and from j to i are counted as one).

More formally, if d is the matrix of shortest paths, where di,j is the length of the shortest path between vertices i and j (1≤i<j≤n), then you need to print the k-th element in the sorted array consisting of all di,j, where 1≤i<j≤n.

Input
The first line of the input contains three integers n,m and k (2≤n≤2⋅105, n−1≤m≤min(n(n−1)2,2⋅105), 1≤k≤min(n(n−1)2,400) — the number of vertices in the graph, the number of edges in the graph and the value of k, correspondingly.

Then m lines follow, each containing three integers x, y and w (1≤x,y≤n, 1≤w≤109, x≠y) denoting an edge between vertices x and y of weight w.

It is guaranteed that the given graph is connected (there is a path between any pair of vertices), there are no self-loops (edges connecting the vertex with itself) and multiple edges (for each pair of vertices x and y, there is at most one edge between this pair of vertices in the graph).

Output
Print one integer — the length of the k-th smallest shortest path in the given graph (paths from the vertex to itself are not counted, paths from i to j and from j to i are counted as one).

Examples
Input
6 10 5
2 5 1
5 3 9
6 2 2
1 3 1
5 1 8
6 5 10
1 6 5
6 4 6
3 6 2
3 4 5
Output
3
Input
7 15 18
2 6 3
5 7 4
6 5 4
3 6 9
6 7 7
1 6 4
7 1 6
7 2 1
4 3 2
3 2 8
5 3 6
2 5 5
3 7 9
4 1 8
2 1 1
Output
9
题目大意：给出一张无向图，求这个图中所有路径中第$k$小路径的长度。
思路：把边按照权值进行排序，取最小的$k$条边，记录这些边的顶点，那么最多可以得到$800$个顶点，跑$floyd$算法，然后将得到的结果排序输出第$k$小即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
struct edge
{
int from,to;
ll dis;
bool operator <(const edge &a)const
{
return dis<a.dis;
}
}Edge[maxn];
vector<ll> vec;
ll a[805],s[805][805];
int len,n,m,k;
void floyd()
{
for(int k=1;k<=len;k++)
for(int i=1;i<=len;i++)
for(int j=1;j<=len;j++)
s[i][j]=min(s[i][j],s[i][k]+s[k][j]);
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<m;i++)
scanf("%d%d%lld",&Edge[i].from,&Edge[i].to,&Edge[i].dis);
sort(Edge,Edge+m);
for(int i=0;i<k;i++)
{
a[len++]=Edge[i].from;
a[len++]=Edge[i].to;
}
sort(a,a+len);
len=unique(a,a+len)-a;
for(int i=1;i<=len;i++)
for(int j=1;j<=len;j++)
s[i][j]=1e16;
int t1,t2;
for(int i=0;i<k;i++)
{
t1=upper_bound(a,a+len,Edge[i].from)-a;
t2=upper_bound(a,a+len,Edge[i].to)-a;
s[t1][t2]=s[t2][t1]=Edge[i].dis;
}
floyd();
for(int i=1;i<=len;i++)
for(int j=i+1;j<=len;j++)
if(s[i][j]!=1e16)
vec.push_back(s[i][j]);
sort(vec.begin(),vec.end());
printf("%lldn",vec[k-1]);
return 0;
}

最后

以上就是朴实路灯最近收集整理的关于codeforces 1196F K-th Path 思维+floyd的全部内容，更多相关codeforces内容请搜索靠谱客的其他文章。