1
初级启示者
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
g[u].push_back((edge){v,w});
g[v].push_back((edge){u,w});
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<g[i].size();j++)
{
g[i][j].adj=i,g[j][i].adj=j;
dijkstra();
ans=max(ans,dis[n]);
g[i][j].adj=j,g[j][i].adj=i;
}
}
cout<<ans;
return 0;
}主函数代码，dij函数没问题，不给出。但不知道为什么在for循环里执行时会死循环啊？？？？
主函数里的ans是每次删边的最短路径权值的最大值，g是存图的邻接表，第二个大for循环是为了遍历图删边的。
（话说连O(n³)蓝题都能被卡住，我是不是废了
1
中级守护
首先吐槽一遍题目描述，这什么鬼？？？
简直狗屁不通
我重新描述一下题目，相信很多人能ac
1-n有m条边
但m条边中可能会有一条边无法通过
求出时间t，保证时间t内无论哪条路无法通过，都能满足有一条从1-n路径总时间小于或等于t的最短路
但是倘若选择一条总时间小与t的路线，则必有一条边，使其无法从1到达n
举个例子：! 
最短路很明显，1-4-5
总时间为12
但是当其中有一条边堵车的时候，就无法通过
那么，我们就可以取其中一条边，将其“无视”
假设我们取4-5断掉，那么得到此时的最短路为：1-4-2-5
总时间为14
但是注意！此时答案并没有出来，14仍为错误答案！
当1-4这条边堵住的时候，1-4-5和1-4-2-5都无法通过，从而无法满足t = 14时，取任意一条路塞住，有一条总时间小于或等于的t的最短路
所以我们再换取另一条边：1-4
堵住~
然后再跑一遍，此时最短路为：1-3-4-5 t = 20；
此时就满足题目条件了，怎么堵都会存在一条最短路
综上：我们就能够得出写法。
先跑一遍最短路，将最短路的路径记录下来，
然后枚举每一条最短路的边，将其断掉，记录此时的1-n的时间
取其中最大的一个时间即为所求
代码如下：
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int n,m,Cnt,Flag,Ans;
int Head[1005],Dis[1005],Cut[1005][1005],f[1005],Inq[1005];
struct Node{
int to,Next,w;
}e[1000005];
inline void Insert(int u,int v,int w){
e[++Cnt].to = v;
e[Cnt].Next = Head[u];
Head[u] = Cnt;
e[Cnt].w = w;
}
inline void Spfa(){
queue<int> q;
memset(Inq,0,sizeof(Inq));
memset(Dis,INF,sizeof(Dis));
q.push(1);
Dis[1] = 0;
while(!q.empty()){
int u = q.front();
q.pop();
Inq[u] = 0;
for(int i=Head[u];i;i=e[i].Next){
if(Cut[u][e[i].to] == 0 && Dis[e[i].to] > Dis[u] + e[i].w){
if(!Flag)f[e[i].to] = u;
Dis[e[i].to] = Dis[u] + e[i].w;
if(!Inq[e[i].to]){
Inq[e[i].to] = 1;
q.push(e[i].to);
}
}
}
}
}
inline int Read(){
int Out = 0,f = 1;char ch = getchar();
while(!isdigit(ch)){if(ch == '-')f = -1;ch = getchar();}
while(isdigit(ch)){Out = Out * 10 + ch - '0';ch = getchar();}
return Out * f;
}
int main(){
n = Read();
m = Read();
for(int i=1;i<=m;i++){
int u = Read(),v = Read(),w = Read();
Insert(u,v,w);
Insert(v,u,w);
}
Spfa();
Flag = 1;
for(int i=n;i!=1;i=f[i]){
Cut[f[i]][i] = 1;
Cut[i][f[i]] = 1;
Spfa();
Cut[f[i]][i] = 0;
Cut[i][f[i]] = 0;
Ans = Ans > Dis[n] ? Ans:Dis[n];
}
printf("%d\n",Ans);
return 0;
}
0
新手天翼
shui
0
缔造者之神
还上问答吗？
