蒟蒻不理解超源是什么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;
}
}