有如下代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
struct node {
int to, w;
};
int dis[N];
vector <node> p[N];
queue <int> q;
bool vis[N];
void spfa(int s) {
memset(dis, 0x3f, sizeof(dis));
q.push(s), dis[s] = 0, vis[s] = true;
while (!q.empty()) {
int t = q.front(); q.pop();
vis[t] = false;
for (auto i : p[t])
if (dis[i.to] > dis[t] + i.w) {
dis[i.to] = dis[t] + i.w;
if (!vis[i.to]) q.push(i.to);
}
}
}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 1, u, v, w; i <= m; i++)
cin >> u >> v >> w, p[u].push_back({v, w});
spfa(s);
for (int i = 1; i <= n; i++)
cout << (dis[i] == dis[0] ? 2147483647 : dis[i]) << " ";
return 0;
}
其中对于 vis 数组根本没有赋值为 1 的操作,却也能过,也就是说只松弛了 s 的出边?是数据太水了还是这个写法就是对的?
PS:提交到加强版也 A 了两个点