不知为何一旦数据是No就会炸掉 所以60pts
查看原帖
不知为何一旦数据是No就会炸掉 所以60pts
250461
SSSSSaber楼主2020/5/5 16:37

蒟蒻不理解超源是什么QAQ

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int num[10100];
int n,m,head[10100],cnt,fer[10100],dis[10100],que[10100];
struct edge{
    int from,to;
    int val;
}e[2020000];
void addedge(int x,int y,int w)
{
    e[++cnt].from =head[x];
    head[x]=cnt;
    e[cnt].to =y;
    e[cnt].val =w;
}
bool spfa(int now)
{
    memset(dis,0x6f,sizeof(dis));
    dis[now]=0;
    int front=0;
    int tail=1;
    que[tail]=now;
    while(front<tail)
    {
        ++front;
        int a=que[front];
        fer[a]=0;num[a]++;
        if(num[a]>n-1)
        {
            return 0;
        }
        for(int i=head[a];i;i=e[i].from)
        {
            int v=e[i].to;
            if(dis[v]>dis[a]+e[i].val )
            {
                dis[v]=dis[a]+e[i].val ;
                if(!fer[v])
                {
                    que[++tail]=v;
                    fer[v]=1;
                }
            }
        }
    }
    return 1;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int fer;
        int ai,bi,ci;
        cin>>fer;
        if(fer==1)
        {
            cin>>ai>>bi>>ci;
            addedge(bi,ai,-ci);
        }
        if(fer==2)
        {
            cin>>ai>>bi>>ci;
            addedge(ai,bi,ci);
        }
        if(fer==3)
        {
            cin>>ai>>bi;
            addedge(ai,bi,0);
            addedge(bi,ai,0);
        }
    }
{
  if(!spfa(i))
  {
     cout<<"No";
  }
    return 0;
}
    cout<<"Yes";
    return 0;
}
}
2020/5/5 16:37
加载中...