poj3259

发布 : 2020-06-23 分类 : Bellman-Ford & SPFA 浏览 :

传送门

第一种方法:Bellman-Ford

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m, w;
#define MAX 10005
struct node{
int u, v, t;
}p[5210];

void Bellman_Ford(){
int dis[505];
memset(dis, MAX, sizeof(dis));
dis[1] = 0;
for(int i = 1; i < n; i++)
for(int j = 1; j <= 2 * m + w; j++)
dis[p[j].v] = min(dis[p[j].v], dis[p[j].u] + p[j].t);
int flag = 0;
for(int i = 1; i <= 2 * m + w; i++)
if(dis[p[i].v] > dis[p[i].u] + p[i].t){
flag = 1;
break;
}
if(flag) cout << "YES" << endl;
else cout << "NO" << endl;
}

int main(){
int f;
cin >> f;
while(f--){
cin >> n >> m >> w;
for(int i = 1; i <= 2 * m - 1; i += 2){
cin >> p[i].u >> p[i].v >> p[i].t;
p[i + 1].v = p[i].u;
p[i + 1].u = p[i].v;
p[i + 1].t = p[i].t;
}
for(int i = 2 * m + 1; i <= 2 * m + w; i++){
cin >> p[i].u >> p[i].v >> p[i].t;
p[i].t = -p[i].t;
}
Bellman_Ford();
}
return 0;
}

/*
Input:
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
Output:
NO
YES
*/
本文作者 : preccrep
原文链接 : https://preccrep.github.io/2020/06/23/poj3259/
版权声明 : 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
留下足迹

博客已萌萌哒运行(●'◡'●)ノ♥
Theme - BMW | Made With 💗 | Powered by GodBMW