1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 using namespace std;
6 struct edge{
7 int to;
8 int next;
9 int len;
10 }qwq[
100005];
11 queue<
int>
pq;
12 int edge_cnt=
0,n,m,head[
100005],
in[
100005],stk[
100005],dist[
100005];
13 bool spfa()
14 {
15 memset(
in,
0,
sizeof(
in));
16 memset(stk,
0,
sizeof(stk));
17 memset(dist,-
1,
sizeof(dist));
18 dist[
0]=
0;
19 while(!
pq.empty())
20 {
21 pq.pop();
22 }
23 pq.push(
0);
24 in[
0]++
;
25 stk[
0]=
1;
26 while(!
pq.empty())
27 {
28 int qaq=
pq.front();pq.pop();
29 stk[qaq]=
0;
30 for(
int i = head[qaq];i!=-
1;i=
qwq[i].next)
31 {
32 int v=
qwq[i].to;
33 if(dist[v]<dist[qaq]+
qwq[i].len)
34 {
35 dist[v]=dist[qaq]+
qwq[i].len;
36 if(!
stk[v])
37 {
38 pq.push(v);
39 in[v]++
;
40 stk[v]=
1;
41 if(
in[v]>n+
1){
42 return false;
43 }
44 }
45 }
46 }
47 }
48 return true;
49 }
50 void add(
int x,
int y,
int z)
51 {
52 qwq[edge_cnt].to=
y;
53 qwq[edge_cnt].next=
head[x];
54 qwq[edge_cnt].len=
z;
55 head[x]=edge_cnt++
;
56 }
57 int main()
58 {
59 scanf(
"%d%d",&n,&
m);
60 memset(head,-
1,
sizeof(head));
61 edge_cnt=
0;
62 for(
int i =
0 ; i < m ;i++
)
63 {
64 int a,b,c;
65 scanf(
"%d%d%d",&a,&b,&
c);
66 add(a,b,c);
67 }
68 if(!spfa())printf(
"-1\n");
69 return 0;
70 }
转载于:https://www.cnblogs.com/MekakuCityActor/p/8999538.html
相关资源：各显卡算力对照表！
