社区讨论
求助,只过了一个点
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 条回复,欢迎继续交流。
正在加载回复...