4019: Graph
时间限制: 1 Sec 内存限制: 128 MB
题目描述
小 Y 又开始了一段旅途。
这次，他要经过一个图，从1号点到达n号点，每个点设有休息站。
小 Y 计划用最多k天走完全程，除第k天外，每一天小 Y 都必须在休息站过夜。所以，一段路必须在同一天走完。
小 Y 的体力有限，他希望走的路程最大的一天中走的路尽可能少，请求出这个最小值。
输入
第一行三个整数n、m、k表示图的顶点数、边数、天数。
从第二行开始，之后的 m 行，每行三个整数 ui、vi、wi表示从 ui和 vi间有一条双向道路，长度为wi。
输出
一行一个正整数，如果小 Y 能走完全程，输出走的路程最大的一天中走的路程最小值，否则输出−1。
样例输入 Copy
3 2 4
3 2 4
1 2 1
样例输出 Copy
4
提示
对于100%的数据，2≤n≤k≤7500，0≤m≤200000，1≤wi≤109；保证没有重边和自环。
解析:
经典的SPFA题目,不详细解释,具体见过去SPFA教程
#include<bits/stdc++.h>
using namespace std;
int read(){
char c=getchar();int ans=0;
while(!isdigit(c)) c=getchar();
while(isdigit(c)){ans=ans*10+c-'0';c=getchar();}
return ans;
}
int n,m,k;
struct Node{
int u,v,w;
}a[200005];
int fa[7505];
bool cmp(Node x,Node y){return x.w<y.w;}
void init(){
n=read();m=read();k=read();
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++){
a[i].u=read();a[i].v=read();a[i].w=read();
}
sort(a+1,a+1+m,cmp);
}
int find_fa(int x){return x!=fa[x]?fa[x]=find_fa(fa[x]):x;}
void union_set(int x,int y){
int fx=find_fa(x),fy=find_fa(y);
fa[fx]=fy;
}
int ans;
int main(){
init();ans=0;
for(int i=1;i<=m;i++){
int fx=find_fa(a[i].u),fy=find_fa(a[i].v);
if(fx!=fy){k--;ans=a[i].w;}
if(k<0) break;
union_set(fx,fy);
if(find_fa(1)==find_fa(n)){
cout<<ans<<endl;return 0;
}
}
cout<<-1<<endl;
return 0;
}
