社区讨论

求助,只过了一个点

P2850[USACO06DEC] Wormholes G参与者 4已保存回复 10

讨论操作

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

当前回复
10 条
当前快照
1 份
快照标识符
@mi7rt8ue
此快照首次捕获于
2025/11/21 02:34
4 个月前
此快照最后确认于
2025/11/21 02:34
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
#define ll long long
#define ri register int
#define INF 0x7fffffff
#define nl putchar('\n')
#define N 100010
using namespace std;
template<class T> inline void read(T &x)
{
	x=0;
	register char c=getchar();
	register bool f=0;
	while (!isdigit(c)) f ^=c=='-',c=getchar();
 	while (isdigit(c)) x=x*10+c-'0',c=getchar();
	if(f)x=-x;
}
template <class T> inline void print(T x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar('0'+x%10);
}
struct node{
	int to,next,w;
}edge[N];
int head[N],inq[N],dis[N];
bool vis[N];
int m,n,w,f,tot=0,t;
inline int addedge(int a,int b,int c){
	tot++;
	edge[tot].to=b;
	edge[tot].w=c;
	edge[tot].next=head[a];
	head[a]=tot;
}
inline void SPFA(){
	queue<int>q;
	memset(dis,127,sizeof(dis));
	memset(inq,0,sizeof(inq));
	memset(vis,false,sizeof(vis));
	dis[1]=0;inq[1]=0;q.push(1);vis[1]=true;
	while(!q.empty()){
		int x=q.front();q.pop();
		vis[x]=false;
		for(ri i=head[x];i;i=edge[i].next){
			int z=edge[i].to;
			if(dis[z]>dis[x]+edge[i].w){
				dis[z]=dis[x]+edge[i].w;
				inq[z]++;
				if(inq[z]>n){
					puts("YES");
					return;
				}
				if(!vis[x]){
					vis[x]=true;
					q.push(z);
				}
			}
		}
	}
	puts("NO");
	return;
}
int main(){
	read(t);
	while(t--){
		tot=0;
		memset(head,0,sizeof(head));
		read(n);read(m);read(w);
		for(ri i=1;i<=m;i++){
			int a,b,c;
			read(a);read(b);read(c);
			addedge(a,b,c);
			addedge(b,a,c);
		}
		for(ri i=1;i<=w;i++){
			int a,b,c;
			read(a);read(b);read(c);
			addedge(a,b,-c);
		}
		SPFA();
	}
	return 0;
}

回复

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

正在加载回复...