奇怪了,为什么pow(2,31)-1wa了#3
查看原帖
奇怪了,为什么pow(2,31)-1wa了#3
1183187
sxhy楼主2024/3/18 23:32

把代码改为cout <<"2147483647 ";就对了....

#include<bits/stdc++.h>
using namespace std;
const int N = 410000;
const int N1 = 500010;
typedef long long ll;
int n,m,s,d[N],vis[N];
struct edge {
	int b,w,ne;
}e[N1];
struct node {
	int x,d;
	bool operator <(const node& qt)const {
		return d > qt.d;
	}
};
int h[N1],idx;
vector<int>v;
priority_queue<node>q;
inline void add(int a,int b,int c) {
	e[idx] = {b,c,h[a]};
	h[a] = idx++;
}

inline void dj() {
	q.push({s,0});
	d[s] = 0;
	while (!q.empty()) {
		int u = q.top().x, d1 = q.top().d;
		q.pop();
		if (vis[u]) { continue; }//*
		vis[u] = 1;
		for (int i = h[u]; ~i; i = e[i].ne)
		{
			int v = e[i].b,w=e[i].w;
			if (d[v] > d[u] + w) {//*
				d[v] = d[u] + w;
				q.push({v,d[v]});
			}
        }


	}

}

int main() {
	int a, b, c;
	memset(h, -1, sizeof(h));
	memset(d,0x3f,sizeof(d));
	cin >> n >> m>>s ;
	for (int i = 1; i <= m; i++) {
		cin >> a >> b >> c;
		add(a, b, c);
	}
	dj();
	
	for (int i = 1; i <= n; i++) {
		if (d[i] != 0x3f3f3f3f)
			printf("%d ", d[i]);
		else cout << (int)pow(2, 31) - 1<<" ";
	}
}
2024/3/18 23:32
加载中...