|
ht)
41 dis[e[j].to] = dis[e[j].from] + e[j].weight;
42 }
43 }
44 for (int i = 1; i <= tot; i++)
45 if (dis[e[i].to] > dis[e[i].from] + e[i].weight)
46 return 0;
47 return 1;
48 }
49 int main()
50 {
51 cin >> t;
52 while (t--)
53 {
54 tot = 0;
55 memset(e, 0, sizeof(e));
56 memset(dis, 0, sizeof(dis));
57 n = 0, m = 0, w = 0;
58 cin >> n >> m >> w;
59 for (int i = 1; i <= m; i++)
60 {
61 int x, y, z;
62 cin >> x >> y >> z;
63 add(x, y, z);
64 add(y, x, z);
65 }
66 for (int i = 1; i <= w; i++)
67 {
68 int x, y, z;
69 cin >> x >> y >> z;
70 add(x, y, 0 - z);
71 }
72 if (Bellman_Ford())
73 cout << "NO" << endl;
74 else
75 cout << "YES" << endl;
76 }
77 return 0;
78 }
算法优点
算法缺点
-
很慢，时间复杂度O(nm),而且求的是单元最短路，一般只用来判断是否有负权回路，而且实际使用时往往要使用他的队列优化，也就是SPFA
（今天刚注册的博客，立刻就像写一篇博客试试，然而实际写起来才觉得没那么简单，写完后返回来以看就发现了很多缺陷，而且也不太清楚从何改起.......不过我相信写博客同样也是熟能生巧的，只要一直写下去，想必将来也能写出优秀的博客）
|