家人，问题好像是一条路可以走多次，然后次短路就是1-5-1-5。（就是这个~~sb~~去了农场又回来又去）
by CityFish @ 2023-09-30 09:45:11
没看懂你这个Dijkstra,感觉你这是SPFA
这是我AC的Dijkstra:
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 9999;
const int INF = 0x3f3f3f;
struct Edge{
int to,w;
};
vector<Edge> es[maxn];
priority_queue<pair<int,int> > q;
int N,R,firdis[maxn],secdis[maxn],vis[maxn];
void Dijkstra(){
for(int i = 1;i <= N;i++) firdis[i] = INF,secdis[i] = INF;
for(auto e : es[1]){
secdis[e.to] = 3*e.w;
}
firdis[1] = 0;
q.push(make_pair(0,1));
while(!q.empty()){
int u = q.top().second;q.pop();
if(vis[u]) continue;
vis[u] = true;
for(auto e : es[u]){
int v = e.to,w = e.w;
if(firdis[v] > firdis[u]+w){
secdis[v] = min(secdis[v],min(firdis[v],secdis[u]+w));firdis[v] = firdis[u]+w;
q.push(make_pair(-firdis[v],v));
}
else if(firdis[v] == firdis[u]+w){
}
else if(secdis[v] > firdis[u]+w){
secdis[v] = firdis[u]+w;
}
}
/*
system("cls");
cout<<"Considering "<<u<<" :"<<endl;
cout<<" firdis secdis"<<endl;
for(int i = 1;i <= N;i++){
cout<<i<<" ";
if(firdis[i] == INF) cout<<"INF";
else cout<<firdis[i];
cout<<" ";
if(secdis[i] == INF) cout<<"INF"<<endl;
else cout<<secdis[i]<<endl;
}
int ok;cin>>ok;
*/
}
}
int main(){
cin>>N>>R;
for(int i = 1;i <= R;i++){
int u,v,w;
cin>>u>>v>>w;
es[u].push_back(Edge{v,w});
es[v].push_back(Edge{u,w});
}
Dijkstra();
cout<<secdis[N]<<endl;
return 0;
}
```
by CityFish @ 2023-09-30 10:14:00
@[CityFish](/user/492030) 感谢！！！！
对不起才看到QAQ
by carp_oier @ 2023-10-20 16:33:13
@[CityFish](/user/492030) 我的 dijkstra 的思路是存三个值，一个是点的编号，一个是距离，一个是它的类型(0 代表最长路,1 代表次长路)
by carp_oier @ 2023-10-20 16:34:25