为啥要用手写队列???
by LYM20114 @ 2022-07-14 10:30:51
```
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n,m,s,t;
vector <int> V[2505];
int G[2505][2505];
bool vis[2505];
unsigned int res[2505];
void spfa(int x){
for(int i = 1;i <= n;i++)
res[i] = 0x7fffffff;
queue <int> qx;
qx.push(x);
vis[x] = 1;
res[x] = 0;
while(!qx.empty()){
int nx = qx.front();
qx.pop();
vis[nx] = 0;
for(int i = 0;i < V[nx].size();i++){
int xx = V[nx][i];
if(res[xx] > res[nx] + G[xx][nx]){
res[xx] = res[nx] + G[xx][nx];
if(!vis[xx]){
vis[xx] = 1;
qx.push(xx);
}
}
}
}
}
int main(){
cin >> n >> m >> s >> t;
for(int i = 1;i <= m;i++){
int u,v,w;
cin >> u >> v >> w;
G[u][v] = w;
G[v][u] = w;
V[u].push_back(v);
V[v].push_back(u);
}
spfa(s);
cout << res[t];
return 0;
}
by LYM20114 @ 2022-07-14 10:31:19
@[LYM2011](/user/531776) 知周所众,手写队列常数小
by Hoks @ 2022-10-26 21:23:00