大意：n个点p条边的无向图，求在删去k条边后使1和n号点联通路径上的最长边最小值。
一开始理解错题意以为是分层图求最短路径，结果写完发现k太大了发现事情没有那么简单（讨厌英语题面！）
说一下解法吧，二分答案，尽量小，每次二分完跑最短路径，但是要重置边权。即把比答案小的边改为0，比答案大的改为1，若最短路径比k大，就加答案；反之亦然。
（还好都有最短路径算没白写）
唯一的一点技巧：最初想着每次找完mid把所有边的权值改一下，觉得太麻烦了，那么就每次dijkstra加点的时候判断一下吧！（反正又占不了多少时间……吧）
#include<iostream> #include<vector> #include<cstdio> #include<queue> #include<cctype> #include<algorithm> #include<cstring> using namespace std; inline int read() { int x=0,w=0;char c=getchar(); while(!isdigit(c))w|=c=='-',c=getchar(); while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar(); return w?-x:x; } namespace star { const int maxn=1010,maxm=1000010; int n,m,k; int ecnt,head[maxn],nxt[maxm],t[maxm],val[maxm]; inline void addedge(int from,int to,int dis){ t[++ecnt]=to;nxt[ecnt]=head[from];head[from]=ecnt;val[ecnt]=dis; } typedef pair<int,int> pii; int dis[maxn]; inline void dijkstra(int mid) { priority_queue<pii,vector<pii >,greater<pii > > q; q.push(make_pair(0,1)); memset(dis,0x3f3f3f3f,sizeof dis); dis[1]=0; while(!q.empty()) { int x=q.top().second;q.pop(); for(int i=head[x];i;i=nxt[i]){ int u=t[i]; if(dis[u]>dis[x]+(val[i]>mid)){ dis[u]=dis[x]+(val[i]>mid); q.push(make_pair(dis[u],u)); } } } } inline void work() { n=read(),m=read(),k=read(); int mlen=0; for(int a,b,c,i=1;i<=m;i++) { a=read(),b=read(),c=read(); mlen=max(mlen,c); addedge(a,b,c); addedge(b,a,c); } int l=0,r=mlen; while(l<r){ int mid=l+r>>1; dijkstra(mid); if(dis[n]==0x3f3f3f3f){ printf("-1 ");return; } if(dis[n]>k)l=mid+1; else r=mid; } printf("%d ",l); } } int main() { star::work(); return 0; } /* 5 7 1 1 2 5 3 1 4 2 4 8 3 2 3 5 2 9 3 4 7 4 5 6 */