社区讨论
关于数组初始化的疑惑
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 条回复,欢迎继续交流。
正在加载回复...