传送门
这个题意描述的狗屁不通。。。其实大概就是
1-n有m条边 但m条边中可能会有一条边无法通过 求出时间t，保证时间t内无论哪条路无法通过，都能满足有一条从1-n路径总时间小于或等于t的最短路然后思路就很简单啊，我们枚举最短路的边，依次断掉每一条同时再跑一遍最短路，统计一下最大值即可。
通过一个pre数组可以实现枚举最短路的边，原理很简单：最短路上的每一个点，最后被松弛的那一次就是最关键的边。
#include<bits/stdc++.h> #define N 1005 #define M 10000005 using namespace std; int n,m,first[N],tot,zdl[N],max_cost,pre[N]; const int INF=0x3f3f3f3f; bool vis[N],is_first; struct node { int from,to,next,val; }edge[2*M]; inline void addedge(int x,int y,int z) { tot++; edge[tot].to=y; edge[tot].from=x; edge[tot].next=first[x]; edge[tot].val=z; first[x]=tot; } queue <int> q; int spfa(int s) { memset(zdl,INF,sizeof(zdl)); memset(vis,false,sizeof(vis)); while(q.size()) q.pop(); q.push(s); zdl[s]=0; vis[s]=true; while(!q.empty()) { int now=q.front(); q.pop(); vis[now]=false; for(int u=first[now];u;u=edge[u].next) { int v=edge[u].to; if(zdl[now]+edge[u].val<zdl[v]) { if(is_first) pre[v]=u; zdl[v]=zdl[now]+edge[u].val; if(vis[v]==false) { q.push(v); vis[v]=true; } } } } return zdl[n]; } int main() { ios::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); cin>>n>>m; for(int i=1;i<=m;i++) { int a,b,c; cin>>a>>b>>c; addedge(a,b,c); addedge(b,a,c); } is_first=true; max_cost=spfa(1); is_first=false; for(int i=pre[n];i;i=pre[edge[i].from]) { int old=edge[i].val; edge[i].val=INF; max_cost=max(max_cost,spfa(1)); edge[i].val=old; } cout<<max_cost; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9478388.html
相关资源：各显卡算力对照表！