社区讨论

为啥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 条回复,欢迎继续交流。

正在加载回复...