-
Notifications
You must be signed in to change notification settings - Fork 0
/
BOJ_1865.py
88 lines (81 loc) · 2.3 KB
/
BOJ_1865.py
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
83
84
85
86
87
88
# 1865
# import heapq
# import sys
# INF = sys.maxsize
# input = sys.stdin.readline
#
# def dijkstra(start):
# q = []
# heapq.heappush(q, [0, start])
#
# dist = [INF for _ in range(n+1)]
#
# while q:
# weight, here = heapq.heappop(q)
#
# if here == start and weight < 0:
# dist[start] = -1
# return dist
#
# for there, w in road[here]:
# next_weight = w + weight
# if dist[there] > next_weight:
# dist[there] = next_weight
# heapq.heappush(q, [next_weight, there])
#
# for there, w in worm[here]:
# next_weight = (-1 * w) + weight
# if dist[there] > next_weight:
# dist[there] = next_weight
# heapq.heappush(q, [next_weight, there])
#
# return dist
#
# for _ in range(int(input())):
# # n = 지점 수, m = 도로 수, w = 웜홀 수
# # 도로는 쌍방향
# # 웜홀은 방향 존재
#
# n, m, w = map(int, input().split())
# road = [[] for _ in range(n+1)]
# worm = [[] for _ in range(n+1)]
# for _ in range(m):
# s, e, t = map(int, input().split())
# road[s].append([e, t])
# road[e].append([s, t])
# for _ in range(w):
# s, e, t = map(int, input().split())
# worm[s].append([e, t])
#
# for i in range(1, n+1):
# if dijkstra(i)[i] == -1:
# print("YES")
# break
# if i == n:
# print("NO")
import sys
INF = sys.maxsize
input = sys.stdin.readline
def belman():
dist = [INF for _ in range(n+1)]
dist[1] = 0
for compare_with_n in range(1, n+1):
for here in range(1, n+1):
for there, weight in graph[here]:
next_weight = weight + dist[here]
if dist[there] > next_weight:
dist[there] = next_weight
if compare_with_n == n:
return "YES"
return "NO"
for _ in range(int(input())):
n, m, w = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
s, e, t = map(int, input().split())
graph[s].append([e, t])
graph[e].append([s, t])
for _ in range(w):
s, e, t = map(int, input().split())
graph[s].append([e, -t])
print(belman())