85pts,三个点TLE求助
查看原帖
85pts,三个点TLE求助
767099
WEXI7111楼主2022/11/11 23:11
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int h[N],to[N],w[N],nxt[N],idx;
void add(int u,int v,int wt)
{
    to[++idx]=v;w[idx]=wt;nxt[idx]=h[u];h[u]=idx;
    return;
}
int dis[N],cnt[N];
bool inq[N];
int n,m;
bool spfa(int s)
{
    stack<int>q;
    dis[s]=0;q.push(s);inq[s]=1;
    while(!q.empty())
    {
        int a=q.top();q.pop();
        inq[a]=0;
        for(int i=h[a];i!=-1;i=nxt[i])
        {
            int e=to[i];
            if(dis[e]>dis[a]+w[i])
            {
                dis[e]=dis[a]+w[i];
                cnt[e]=cnt[a]+1;
                if(cnt[e]>n) return 1; 
                if(!inq[e]) {q.push(e);inq[e]=1;}
            }
        }
    }
    return 0;
}
int main()
{
    memset(h,-1,sizeof(h));
    memset(dis,0x3f,sizeof(dis));
    cin>>n>>m;
    while(m--)
    {
        int tp,a,b,c;
        cin>>tp>>a>>b;
        if(tp==1) {cin>>c;add(a,b,-c);}
        if(tp==2) {cin>>c;add(b,a,c);}
        if(tp==3) add(a,b,0),add(b,a,0);
    }
    for(int i=1;i<=n;i++) add(0,i,0);
    if(spfa(0)) cout<<"No";
    else cout<<"Yes";
    return 0;
}
2022/11/11 23:11
加载中...