Description
Farmer John打算将电话线引到自己的农场，但电信公司并不打算为他提供免费服务。于是，FJ必须为此向电信公司支付一定的费用。 FJ的农场周围分布着N(1 <= N <= 1,000)根按1..N顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P(1 <= P <= 10,000)对电话线杆间可以拉电话线，其余的那些由于隔得太远而无法被连接。 第i对电话线杆的两个端点分别为A_i、B_i，它们间的距离为 L_i (1 <= L_i <= 1,000,000)。数据中保证每对{A_i，B_i}最多只出现1次。编号为1的电话线杆已经接入了全国的电话网络，整个农场的电话线全都连到了编号为N的电话线杆上。也就是说，FJ的任务仅仅是找一条将1号和N号电话线杆连起来的路径，其余的电话线杆并不一定要连入电话网络。 经过谈判，电信公司最终同意免费为FJ连结K(0 <= K < N)对由FJ指定的电话线杆。对于此外的那些电话线，FJ需要为它们付的费用，等于其中最长的电话线的长度（每根电话线仅连结一对电话线杆）。如果需要连结的电话线杆不超过 K对，那么FJ的总支出为0。 请你计算一下，FJ最少需要在电话线上花多少钱。
Input
第1行: 3个用空格隔开的整数：N，P，以及K
- 第2..P+1行: 第i+1行为3个用空格隔开的整数：A_i，B_i，L_i
Output
- 第2..P+1行: 第i+1行为3个用空格隔开的整数：A_i，B_i，L_i
第1行: 输出1个整数，为FJ在这项工程上的最小支出。如果任务不可能完成， 输出-1
Sample Input
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6
输入说明:
一共有5根废弃的电话线杆。电话线杆1不能直接与电话线杆4、5相连。电话
线杆5不能直接与电话线杆1、3相连。其余所有电话线杆间均可拉电话线。电信
公司可以免费为FJ连结一对电话线杆。
Sample Output
4
输出说明:
FJ选择如下的连结方案：1->3；3->2；2->5，这3对电话线杆间需要的
电话线的长度分别为4、3、9。FJ让电信公司提供那条长度为9的电话线，于是，
他所需要购买的电话线的最大长度为4。
题解：
最后要得到的是最小的第k+1大的边，我们二分边长，设当前边长为tmp，则使比tmp大的边权值变为1，其余的为0，用SPFA求最短路，得到当前情况的权值，如果权值比k小，说明选取的tmp偏大，再继续二分，直到结束。
用dijkstra乱跑超时了。。。最后还是认命用了SPFA。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#define MAXN 2005const int INF=0x3f3f3f3f;
using namespace std;
int n,p;
long long int K;
bool vis[MAXN];
long long int list[10005];
vector<int>To[MAXN];
struct Edge
{int v;int cost;Edge(int _v=0,int _cost=0):v(_v),cost(_cost) {}
};
vector<Edge>E[MAXN];
int now(int x,int y,int t)
{if(E[x][y].cost>t)return 1;return 0;
}
void addedge(int u,int v,int w)
{E[u].push_back(Edge(v,w));
}
int cnt[MAXN];//每个点的入队列次数
int dist[MAXN];
long long int SPFA(long long int t)
{int start=1;memset(vis,false,sizeof(vis));for(int i=1; i<=n; i++)dist[i]=INF;vis[start]=true;dist[start]=0;queue<int>que;while(!que.empty())que.pop();que.push(start);memset(cnt,0,sizeof(cnt));cnt[start]=1;while(!que.empty()){int u=que.front();que.pop();vis[u]=false;for(int i=0; i<E[u].size(); i++){int v=E[u][i].v;if(dist[v]>dist[u]+now(u,i,t)){dist[v]=dist[u]+now(u,i,t);if(!vis[v]){vis[v]=true;que.push(v);if(++cnt[v]>n)return false;}}if(E[u][i].cost>t && dist[v]>dist[u]+1){dist[v]=dist[u]+1;if(!vis[v]){vis[v]=1;que.push(v);}}else if(E[u][i].cost<=t && dist[v]>dist[u]){dist[v]=dist[u];if(!vis[v]){vis[v]=1;que.push(v);}}}}if(dist[n]>=INF)dist[n]=-1;return dist[n];
}
int main()
{int a,b;long long int w,total=0,left,right,outt,tmp,out;scanf("%d%d%lld",&n,&p,&K);for(int i=0; i<p; i++){scanf("%d%d%lld",&a,&b,&w);addedge(a,b,w);addedge(b,a,w);list[total++]=w;}sort(list+0,list+total);left=0,right=list[total-1];while(left<right){tmp=(left+right)/2;outt=SPFA(tmp);if(outt==-1){out=-1;break;}if(outt<=K){out=tmp;right=tmp;}elseleft=tmp+1;}if(out==-1){cout << -1 << endl;return 0;}cout << out << endl;return 0;
}