1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| #include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int M=999999;
int n,m,f[M],flag;
int vis[M],d[M],dis[M];
int nex[M],tot,to[M],head[M],cos[M];
void add(int x,int y,int z)
{
nex[++tot]=head[x];
to[tot]=y;
cos[tot]=z;
head[x]=tot;
}
void spfa(int s)
{
d[1]=s;
vis[s]=1;
memset(dis,128,sizeof(dis));
dis[s]=0;
int h=0,t=1;
do{
h++;
int x=d[h];
vis[x]=0;
for(int i=head[x];i;i=nex[i])
{
int tmp=to[i];
if(dis[tmp]<dis[x]+cos[i])
{
dis[tmp]=dis[x]+cos[i];
if(!vis[tmp])
{
vis[tmp]=1;
d[++t]=tmp;
f[tmp]++;
if(f[tmp]>n)
{
printf("NO");
flag=1;
return;
}
}
}
}
}
while(h<t);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b,t;
scanf("%d%d%d",&a,&b,&t);
if(t==1)
add(b,a,1);
if(t==0)
{
add(a,b,0);
add(b,a,0);
}
if(t==-1)
{
add(a,b,1);
}
}
for(int i=1;i<=n;i++)
add(9999,i,0);
spfa(9999);
int max1=-9999999;
for(int i=1;i<=n;i++)
{
max1=max(max1,dis[i]);
}
if(flag==0)
printf("%d",max1);
}
|
