#include <iostream>#include <cstring>#include <algorithm>#include <queue>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]; // 存储每个点进队的次数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; queue<int> q; q.push(s); st[s] = true; while (q.size()) { int t = q.front(); q.pop(); 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 还没在队列中 { q.push(j); 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;}不用STL实现这个代码
时间: 2024-01-20 14:02:44 浏览: 40
好的,以下是不使用 STL 实现的代码:
```cpp
#include <iostream>
#include <cstring>
#include <queue>
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]; // 存储每个点进队的次数
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;
queue<int> q;
q.push(s);
st[s] = true;
while (q.size()) {
int t = q.front();
q.pop();
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 还没在队列中
{
q.push(j);
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;
}
```