社区讨论

关于数组初始化的疑惑

P3008[USACO11JAN] Roads and Planes G参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi7yjqzk
此快照首次捕获于
2025/11/21 05:43
4 个月前
此快照最后确认于
2025/11/21 05:43
4 个月前
查看原帖
这样把dis初值赋成 INF = 0x3f3f3f3f,最后判dis == INF只有三十分
像某篇题解一样赋成0x7f7f7f7f就过了
但一些题解赋0x3f3f3f3f也过了
CPP
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<iterator>
using namespace std;
const int INF = 0x3f3f3f3f;
int T, R, P, S, cnt, num;
int head[50010], color[50010], visit[50010], ind[50010], dis[50010];
struct edge {
	int to, next, cost;
} a[200010];
struct node {
	int d, u;
	bool operator < (const node &A) const {
		return d > A.d;
	}
};
queue <int > Q;
priority_queue <node> q;
vector <int > p[50010];
void dfs(int u) {
	visit[u] = 1;
	color[u] = cnt;
	p[cnt].push_back(u);
	for(int i = head[u]; i; i = a[i].next) {
		int v = a[i].to;
		if(!visit[v]) {
			dfs(v);
		}
	}
}
void add(int x, int y, int z) {
	a[++num].to = y;
	a[num].cost = z;
	a[num].next = head[x];
	head[x] = num;
}
int main() {
	scanf("%d%d%d%d", &T, &R, &P, &S);
	for(int i = 1; i <= R; i++) {
		int ai, bi, ci;
		scanf("%d%d%d", &ai, &bi, &ci);
		add(ai, bi, ci);
		add(bi, ai, ci);
	}
	for(int i = 1; i <= T; i++) {
		if(!visit[i]) {
			cnt++;
			dfs(i);
		}
	}
	for(int i = 1; i <= P; i++) {
		int ai, bi, ci;
		scanf("%d%d%d", &ai, &bi, &ci);
		add(ai, bi, ci);
		ind[color[bi]]++;
	}
	memset(visit, 0, sizeof(visit));
	memset(dis, 0x3f, sizeof(dis));
	dis[S] = 0;
	Q.push(color[S]);
	for(int i = 1; i <= cnt; i++) {
		if(!ind[i]) Q.push(i);
	}
	while(!Q.empty()) {
		int col = Q.front();
		Q.pop();
		for(int i = 0; i < p[col].size(); i++) {
			q.push(node {dis[p[col][i]], p[col][i]});
		}
		while(!q.empty()) {
			node now = q.top();
			q.pop();
			int u = now.u;
			if(visit[u]) continue;
			visit[u] = 1;
			for(int i = head[u]; i; i = a[i].next) {
				int v = a[i].to;
				if(dis[v] > dis[u] + a[i].cost) {
					dis[v] = dis[u] + a[i].cost;
					if(color[u] == color[v]) q.push(node {dis[v], v});
				}
				if(color[u] != color[v] && (--ind[color[v]]) == 0) Q.push(color[v]);
			}
		}
	}
	for(int i = 1; i <= T; i++) {
		if(dis[i] == INF) {
			printf("NO PATH\n");
		} else printf("%d\n", dis[i]);
	}
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...