题目链接： 点我 题目大意： 可以将T条边的权值改为0，然后选一条从起点到终点最大权值边最小的路。 题目分析： 二分最大权值x，然后dijkstra，遇到小于等于x的路长度为0，大于x的长度为1，总长度不能超过T即可。 PS ：本来写的深搜结果超时了。。。
Problem: 3662 User: ChenyangDu Memory: 516K Time: 110MS Language: C++ Result: Accepted #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; const int maxn = 1000+5,INF = 10000000; int n,m,K,d[maxn]; struct node{int v,d;}; node Node(int v,int d){ node t; t.v = v; t.d = d; return t; } bool operator < (node a,node b){ return a.d>b.d; } struct edge{int t,l;}; edge Edge(int t,int l){ edge r; r.t = t; r.l = l; return r; } vector <edge> G[maxn]; bool bfs(int x){ for(int i=2;i<=n;i++)d[i] = INF; d[1] = 0; priority_queue <node> que; que.push(Node(1,0)); while(!que.empty()){ node t = que.top();que.pop(); if(t.v == n)return true; if(t.d > d[t.v])continue; for(int i=0;i<G[t.v].size();i++){ edge e = G[t.v][i]; int dd = e.l>x?1:0; if(d[e.t] > d[t.v] + dd){ d[e.t] = d[t.v] + dd; if(d[e.t] <= K)que.push(Node(e.t,d[e.t])); } } } return false; } int main(){ //freopen("in.txt","r",stdin); scanf("%d%d%d",&n,&m,&K); for(int a,b,l,i=0;i<m;i++){ scanf("%d%d%d",&a,&b,&l); G[a].push_back(Edge(b,l)); G[b].push_back(Edge(a,l)); } int l = -1,r = INF; while(l<r-1){ int mid = (r+l)>>1; if(bfs(mid))r = mid; else l = mid; } if(r == INF)cout<<"-1"; else cout<<r; return 0; }