所以我想问的是,现在结没结帖?
by Garry_HJR @ 2023-10-07 09:59:38
sxm,我想说的是,你漏了一个条件/wul
by Garry_HJR @ 2023-10-07 10:21:05
首先,最短路更新 $1$ 次,次短路不是,所以你的
`if[vis[u]] continue;`
`vis[u]=1`
是错的,要删掉(17,18行)
by Garry_HJR @ 2023-10-07 10:23:05
接着,你漏了一个致命的要点
那就是你可以从 dis[u]+w 转移到 dis[v]
也可以从 dis[u]+w 转移到 dis2[v] (dis[u]+w>dis[v])
你还可以从 dis2[u]+w 转移到 dis2[v](这个你没写上)
by Garry_HJR @ 2023-10-07 10:29:46
然后还有一个问题,就是怎么处理才能保证不死循环
我们不妨开个标记,如果说更新了就打上标记,否则不打,这样就不会因为无意义操作死循环。
by Garry_HJR @ 2023-10-07 10:30:32
这个,是我改的代码,您参考一下
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<pair<int,int> >e[100005];
int dis[100005],dis2[100005];
bool vis[100005];
priority_queue<pair<int,int>>q;
void dij(int s){
memset(dis,0x3f,sizeof(dis));
memset(dis2,0x3f,sizeof(dis2));
memset(vis,0,sizeof(vis));
dis[s]=0;
q.push({0,s});
while(q.size()){
int u=q.top().second;
q.pop();
//if(vis[u])continue;
//vis[u]=1; 次短路不一定更新1次,应该去掉
for(int i=0;i<e[u].size();i++){
int v=e[u][i].first,w=e[u][i].second;
bool flg=0;//打标记
if(dis[v]>dis[u]+w){
dis2[v]=min(dis2[v],dis[v]);
dis[v]=dis[u]+w;
flg=1;
}
else if(dis2[v]>dis[u]+w&&dis[u]+w!=dis[v]){
dis2[v]=dis[u]+w;
flg=1;
}
else if(dis2[v]>dis2[u]+w){//致命的,你漏掉了这么转移
dis2[v]=dis2[u]+w;
flg=1;
}
if(flg)q.push({-dis[v],v});//如果有标记更新,否则不管。
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
e[u].push_back({v,w});
e[v].push_back({u,w});
}
dij(1);
cout<<dis2[n];
return 0;
}
```
by Garry_HJR @ 2023-10-07 10:33:22
sto sto hjr orz orz
by xiaomai @ 2023-10-13 18:22:25
我居然现在才看见
by xiaomai @ 2023-10-13 18:22:50