卡在55分,求助大佬
查看原帖
卡在55分,求助大佬
348197
绊城烟雨“grz楼主2020/9/13 09:26
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=10000+10;
const int MAXE=10*MAXN;
struct Edge{
    int f,t,lst;ll w;
    Edge(int f=0,int t=0,ll w=0,int lst=0):
        f(f),t(t),w(w),lst(lst){};
};
Edge edge[MAXE];int lst[MAXN],cnt;
void AddEdge(int from,int to,ll w){
    edge[++cnt]=Edge(from,to,w,lst[from]);
    lst[from]=cnt;
    return;
}
int n,m;
bool vis[MAXN],Havevis[MAXN];
ll depth[MAXN];
bool dfs(int i,ll tot){
    vis[i]=true;
    for(int k=lst[i];k!=0;k=edge[k].lst){
        int to=edge[k].t;
        if(Havevis[to]==true)
            continue;
        
        if(vis[to]==true){
            if(tot+edge[k].w>depth[to]){
                return true;
            }
        }
        else{
            depth[to]=tot+edge[k].w;
            if(dfs(to,tot+edge[k].w)==true)
                return true;
        }
    }
    vis[i]=false;
    Havevis[i]=true;
    return false;
}
int main(){
    scanf("%d%d",&n,&m);
    int opt,A,B;
    ll num;
    for(int i=1;i<=n;i++){
        AddEdge(0,i,0);
    }
    for(int i=0;i<m;i++){
        scanf("%d",&opt);
        switch(opt){
            case 1:
                scanf("%d%d%lld",&A,&B,&num);AddEdge(B,A,num);break;
            case 2:
                scanf("%d%d%lld",&A,&B,&num);AddEdge(A,B,-num);break;
            case 3:
                scanf("%d%d",&A,&B);AddEdge(A,B,0);AddEdge(B,A,0);break;

        }
    }
    if(dfs(0,0)==true)
        printf("No");
    else
        printf("Yes");
    
    return 0;
}
2020/9/13 09:26
加载中...