这份代码也能过?
查看原帖
这份代码也能过?
731925
happy_zero楼主2023/10/17 22:26

有如下代码:

#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;
}

其中对于 visvis 数组根本没有赋值为 11 的操作,却也能过,也就是说只松弛了 ss 的出边?是数据太水了还是这个写法就是对的?

PS:提交到加强版也 A 了两个点

2023/10/17 22:26
加载中...