完整代码没有显示出来
时间: 2023-11-16 15:04:48 浏览: 113
抱歉,可能是因为格式问题,我重新发一遍完整代码吧:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1000010, M = 2000010;
const int INF = 0x3f3f3f3f;
int n, m, s, t;
int h[N], e[M], ne[M], w[M], idx; // 邻接表存图
int dist[N]; // 存储起点到各个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定
int cnt[N]; // 存储每个点进队的次数
int q[N], hh, tt; // 双端队列
void add(int a, int b, int c){
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}
bool spfa(){
memset(dist, 0x3f, sizeof dist); // 初始化 dist 数组,全部赋为 INF
dist[s] = 0;
q[tt ++ ] = s; st[s] = true;
while (hh != tt) {
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; ~i; i = ne[i]) // 遍历 t 的所有出边
{
int j = e[i];
if (dist[j] > dist[t] + w[i]) // 如果从 t 点到 j 点的距离更短
{
dist[j] = dist[t] + w[i]; // 更新 dist[j]
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) // 如果存在正环,直接返回 false
return false;
if (!st[j]) // 如果 j 还没在队列中
{
if (hh && q[hh - 1] == j) hh -- ; // 如果从队头插入 j
else q[tt ++ ] = j; // 否则从队尾插入 j
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
return true;
}
int main(){
cin >> n >> m >> s >> t;
memset(h, -1, sizeof h);
while (m -- ) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
if (spfa()) cout << dist[t] << endl;
else puts("无解");
return 0;
}
```
阅读全文