社区讨论
为啥WA了第一个点
P1993小 K 的农场参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mi6xvlh9
- 此快照首次捕获于
- 2025/11/20 12:36 4 个月前
- 此快照最后确认于
- 2025/11/20 12:36 4 个月前
差分约束跑最长路
CPP#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,h,a[10004],head[10004],dis[10004],vis[10004],cnt=0,flag=0;
struct node{
int to,next,w;
}e[1000004];
void add(int u,int v,int w){
e[++cnt].to=v;e[cnt].next=head[u];e[cnt].w=w;head[u]=cnt;
}
void spfa(int u){
if(flag==1) return;
vis[u]=1;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(dis[v]<dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
if(vis[v]){
flag=1;
return;
}
spfa(v);
}
}
}
int main(){
scanf("%d%d",&n,&h);
for(int i=1;i<=h;i++){
int o,x,y,z;
scanf("%d%d%d",&o,&x,&y);
if(o==1) {
scanf("%d",&z);
add(y,x,z);
}else if(o==2){
scanf("%d",&z);
add(x,y,-z);
}else{
add(x,y,0);
add(y,x,0);
}
}
memset(dis,-60,sizeof(dis));
for(int i=1;i<=n;i++){
if(!vis[i]) {
dis[i]=0;
spfa(i);
}
if(flag){
cout<<"No";
return 0;
}
}
cout<<"Yes";
}
/*
第一个点:
10 10
3 9 5
1 6 1 1
1 2 8 0
1 2 8 1
2 4 5 0
1 1 2 1
1 10 5 0
1 10 1 0
2 6 7 0
2 9 3 0
应该输出YES
*/
回复
共 0 条回复,欢迎继续交流。
正在加载回复...