20分代码,不知道为什么炸了。
(玄学Yes改No会有85分的好成绩
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,op,qx,qy,qz,cnt;
int dis[100010];
int num[100010];
bool vis[100010];
struct edge
{
int to;
int next;
int head;
int qw;
}e[4000010];
queue<int>q;
void add(int x,int y,int z)
{
cnt++;
e[cnt].to=y;
e[cnt].qw=z;
e[cnt].head=e[x].head;
e[x].head=cnt;
}
void spfa()
{
q.push(0);
memset(dis,0x3f3f3f3f3f,sizeof(dis));
dis[0]=0;
vis[0]=1;
while(!q.empty())
{
int xx=q.front();
q.pop();
vis[xx]=0;
for(int i=e[xx].head;i;i=e[i].next)
{
int yy=e[i].to;
int zz=e[i].qw;
if(dis[yy]>dis[xx]+zz)
{
dis[yy]=dis[xx]+zz;
num[yy]=num[xx]+1;
if(num[yy]==n)
{
cout<<"No"<<"\n";
return ;
}
if(vis[yy]==0)
{
vis[yy]=1;
q.push(yy);
}
}
}
}
cout<<"Yes"<<"\n";
return ;
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>op;
if(op==1)
{
cin>>qx>>qy>>qz;
add(qx,qy,-qz);
}
if(op==2)
{
cin>>qx>>qy>>qz;
add(qy,qx,qz);
}
if(op==3)
{
cin>>qx>>qy;
add(qx,qy,0);
add(qy,qx,0);
}
}
for(int i=1;i<=n;i++)
{
add(0,i,0);
}
spfa();
return 0;
}