;const int maxn = 10010 ;const int maxm = 50010 ;const int inf = 0x3f3f3f3f ;struct Edge{int v , t , c ;int next ;}edge[maxm<<1] ;int head[maxn] ;int nedge ;int vis[maxn] ;int dis[maxn] ;int n , m , t ;void addedge(int u , int v , int c , int t){edge[nedge].v = v ;edge[nedge].t = t ;edge[nedge].c = c;edge[nedge].next = head[u] ;head[u] = nedge++ ;}bool spfa(int num){queue<int> que;memset(vis , 0 ,sizeof(vis)) ;for(int i = 2;i <= n;i++)dis[i] = inf ;dis[1] = 0 ;que.push(1) ;vis[1] = 1;while(que.size()){int u = que.front() ;que.pop() ;vis[u] = 0 ;for(int i = head[u] ; i != -1 ; i = edge[i].next){if(edge[i].c < num)continue ;int v = edge[i].v ;if(dis[v] > dis[u] + edge[i].t){dis[v] = dis[u] + edge[i].t ;if(!vis[v]){que.push(v) ;vis[v] = 1;}}}}if(dis[n] <= t)return true ;return false ;}int find(int l , int r){while(l <= r){int mid = (l + r) >> 1 ;if(spfa(mid))l = mid + 1 ;else r = mid – 1 ;}return r;}int main(){ // freopen(“in.txt” ,”r” , stdin) ;int T ;scanf(“%d” , &T) ;while(T–){scanf(“%d%d%d” , &n , &m , &t) ;memset(head , -1 , sizeof(head)) ;nedge = 0 ;int ma = 0 ;while(m–){int u , v , c , t ;scanf(“%d%d%d%d” , &u , &v , &c ,&t) ;addedge(u , v , c , t) ;addedge(v , u , c , t) ;ma = max(ma , c) ;}printf(“%d\n” , find(0 , ma)) ;}return 0 ;}
，所有的失败，与失去自己的失败比起来，更是微不足道
