1 //Accepted    508 KB    79 ms      2 //spfa+二分  3 //二分需要的花费cost，把图中大于cost的边设为1,小于cost的边设为0,然后spfa求  4 //最短路，如果小于K则可行，继续二分   5 #include <cstdio>  6 #include <cstring>  7 #include <iostream>  8 #include <queue>  9 #include <cmath> 10 #include <algorithm> 11 using namespace std; 12 /** 13   * This is a documentation comment block 14   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！ 15   * @authr songt 16   */ 17 const int imax_n = 1005; 18 const int imax_e = 20005; 19 const int inf = 100000000; 20 struct node 21 { 22     int u,v,c; 23     node() 24     { 25          26     } 27     node(int u,int v,int c):u(u),v(v),c(c) 28     { 29          30     } 31 }p[imax_e]; 32 int e; 33 bool vis[imax_n]; 34 int head[imax_n]; 35 int next[imax_e]; 36 int dis[imax_n]; 37 int n,m,K; 38 void init() 39 { 40     memset(head,-1,sizeof(head)); 41     memset(next,-1,sizeof(next)); 42     e=0; 43 } 44 void addEdge(int u,int v,int c) 45 { 46     p[e]=node(u,v,c); 47     next[e]=head[u]; 48     head[u]=e++; 49 } 50 bool relax(int u,int v,int c) 51 { 52     if (dis[v]>dis[u]+c) 53     { 54         dis[v]=dis[u]+c; 55         return true; 56     } 57     return false; 58 } 59 queue<int > q; 60 bool spfa(int src,int len) 61 { 62     while (!q.empty()) q.pop(); 63     memset(vis,false,sizeof(vis)); 64     for (int i=1;i<=n;i++) 65     { 66         dis[i]=inf; 67     } 68     dis[src]=0; 69     q.push(src); 70     vis[src]=true; 71     while (!q.empty()) 72     { 73         int pre=q.front(); 74         q.pop(); 75         vis[pre]=false; 76         for (int i=head[pre];i+1;i=next[i]) 77         { 78             int c=p[i].c>len?1:0; 79             if (relax(pre,p[i].v,c) && !vis[p[i].v]) 80             { 81                 vis[p[i].v]=true; 82                 q.push(p[i].v); 83             } 84         } 85     } 86     if (dis[n]<=K) return true; 87     else return false; 88 } 89 int main() 90 { 91     while (scanf("%d%d%d",&n,&m,&K)!=EOF) 92     { 93         init(); 94         int u,v,c; 95         int left=0,right=0,mid; 96         for (int i=1;i<=m;i++) 97         { 98             scanf("%d%d%d",&u,&v,&c); 99             right=right>c?right:c;100             addEdge(u,v,c);101             addEdge(v,u,c);102         }103         if (spfa(1,right)==0)104         {105             printf("-1\n");106             continue ;107         }108         while (left<=right)109         {110             mid=(left+right)/2;111             //printf("left=%d right=%d mid=%d\n",left,right,mid);112             if (spfa(1,mid))113             {114                 right=mid-1;115             }116             else117             {118                 left=mid+1;119             }120         }121         printf("%d\n",right+1);122     }123 }