/
maximum-path-quality-of-a-graph.py
111 lines (103 loc) · 3.88 KB
/
maximum-path-quality-of-a-graph.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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
# Time: O(|V| + |E| + 4^(maxTime/min(times))) = O(|V| + |E| + 4^10)
# Time: O(|V| + |E|)
class Solution(object):
def maximalPathQuality(self, values, edges, maxTime):
"""
:type values: List[int]
:type edges: List[List[int]]
:type maxTime: int
:rtype: int
"""
def iter_dfs(values, adj, maxTime):
lookup, lookup2 = [0]*len(adj), set()
result = 0
stk = [(1, (0, maxTime, 0))]
while stk:
step, args = stk.pop()
if step == 1:
u, time, total = args
lookup[u] += 1
if lookup[u] == 1:
total += values[u]
if not u:
result = max(result, total)
stk.append((4, (u,)))
for v, t in reversed(adj[u]):
if (u, v) in lookup2 or time < t: # same directed edge won't be visited twice
continue
stk.append((3, (u, v)))
stk.append((1, (v, time-t, total)))
stk.append((2, (u, v)))
elif step == 2:
u, v = args
lookup2.add((u, v))
elif step == 3:
u, v = args
lookup2.remove((u, v))
elif step == 4:
u = args[0]
lookup[u] -= 1
return result
adj = [[] for _ in xrange(len(values))]
for u, v, t in edges:
adj[u].append((v, t))
adj[v].append((u, t))
return iter_dfs(values, adj, maxTime)
# Time: O(|V| + |E| + 4^(maxTime/min(times))) = O(|V| + |E| + 4^10)
# Time: O(|V| + |E|)
class Solution2(object):
def maximalPathQuality(self, values, edges, maxTime):
"""
:type values: List[int]
:type edges: List[List[int]]
:type maxTime: int
:rtype: int
"""
def dfs(values, adj, u, time, total, lookup, lookup2, result):
lookup[u] += 1
if lookup[u] == 1:
total += values[u]
if not u:
result[0] = max(result[0], total)
for v, t in adj[u]:
if (u, v) in lookup2 or time < t: # same directed edge won't be visited twice
continue
lookup2.add((u, v))
dfs(values, adj, v, time-t, total, lookup, lookup2, result)
lookup2.remove((u, v))
lookup[u] -= 1
adj = [[] for _ in xrange(len(values))]
for u, v, t in edges:
adj[u].append((v, t))
adj[v].append((u, t))
result = [0]
dfs(values, adj, 0, maxTime, 0, [0]*len(adj), set(), result)
return result[0]
# Time: O(|V| + |E| + 4^(maxTime/min(times))) = O(|V| + |E| + 4^10)
# Time: O(|V| + |E|)
class Solution3(object):
def maximalPathQuality(self, values, edges, maxTime):
"""
:type values: List[int]
:type edges: List[List[int]]
:type maxTime: int
:rtype: int
"""
def dfs(values, adj, u, time, total, lookup, lookup2):
lookup[u] += 1
if lookup[u] == 1:
total += values[u]
result = total if not u else 0
for v, t in adj[u]:
if (u, v) in lookup2 or time < t: # same directed edge won't be visited twice
continue
lookup2.add((u, v))
result = max(result, dfs(values, adj, v, time-t, total, lookup, lookup2))
lookup2.remove((u, v))
lookup[u] -= 1
return result
adj = [[] for _ in xrange(len(values))]
for u, v, t in edges:
adj[u].append((v, t))
adj[v].append((u, t))
return dfs(values, adj, 0, maxTime, 0, [0]*len(adj), set())