为何50分?
code:
#include<bits/stdc++.h>
using namespace std;
const int Maxm=500010;
const int Maxn=100010;
typedef long long ll;
struct Edge
{
int next,to,v;
}e[Maxm];
int n,m,cnt=0;
int dis[Maxn],vis[Maxn],q[Maxn+10],cir[Maxn],head[Maxn];
void adde(int u,int v,int w)
{
e[++cnt].next=head[u];
e[cnt].to=v;
e[cnt].v=w;
head[u]=cnt;
}
bool SPFA()
{
memset(cir,0,sizeof(cir));
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
vis[0]=1;
int l=0,r=n;
q[0]=0;
cir[0]=1;
while(l!=r)
{
int now=q[l];
l++;
if(l==Maxn) l=0;
for(int i=head[now];i;i=e[i].next)
{
if(dis[now]+e[i].v>dis[e[i].to])
{
dis[e[i].to]=dis[now]+e[i].v;
if(++cir[e[i].to]>=n) return false;
if(!vis[e[i].to])
{
vis[e[i].to]=1;
q[r++]=e[i].to;
if(r==Maxn) r=0;
}
}
}
vis[now]=0;
}
return true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int op,u,v;
scanf("%d%d%d",&op,&u,&v);
switch(op)
{
case 1:{
adde(u,v,0);
adde(v,u,0);
break;
}
case 2:{
if(u==v)
{
printf("-1");
return 0;
}else{
adde(u,v,1);
}
break;
}
case 3:{
adde(v,u,0);
break;
}
case 4:{
if(u==v)
{
printf("-1");
return 0;
}else{
adde(v,u,1);
}
break;
}
case 5:{
adde(u,v,0);
break;
}
}
}
for(int i=n;i>0;i--)
{
adde(0,i,1);
}
if(!SPFA())
{
printf("-1");
return 0;
}
ll ans=0;
for(int i=1;i<=n;i++)
{
ans+=dis[i];
}
printf("%lld",ans);
return 0;
}