wa #9 #10 求调
查看原帖
wa #9 #10 求调
1257986
maxiaoxiao111楼主2024/8/10 14:18

是bfs的做法 没看出来哪有错误但就是wa两个点www

#include<bits/stdc++.h>
using namespace std;
int n, m;
long long dis[2][200005];
bool vis[200005];
struct node{
	int to;
	long long x, y;
};
vector <node> a[200005];
void bfs(node p){
	queue <node> q;
	q.push(p);
	while(q.size()){
		p = q.front();
		q.pop();
		if(vis[p.to])continue;
		vis[p.to] = 1, dis[0][p.to] = p.x, dis[1][p.to] = p.y;
		for(auto x : a[p.to]){
			if(vis[x.to])continue;
			q.push({x.to, p.x + x.x, p.y + x.y});
		}
	}
}
int main(){
//	memset(dis, 0x3f, sizeof(dis));
	scanf("%d%d", &n, &m);
	for(int i = 1;i <= m;i++){
		int u, t;
		long long x, y;
		scanf("%d%d%lld%lld", &u, &t, &x, &y);
		a[u].push_back({t, x, y});
		a[t].push_back({u, -x, -y});
	}
	bfs({1, 0, 0});
	for(int i = 1;i <= n;i++){
		if(!vis[i]){
			printf("undecidable\n");
		}else{
			printf("%d %d\n", dis[0][i], dis[1][i]);
		}
	}
	return 0;
}
2024/8/10 14:18
加载中...