1132. 农场派对
摘要
Title: 1132. 农场派对
Tag: 最短路模型、spfa、反向建边
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1132. 农场派对
-
题意
N 头牛要去参加在某农场举行的一场编号为 X 的牛的派对。
有 M 条有向道路，每条路长 Ti；每头牛参加完派对后都必须回到家，每头牛都会选择最短路径。
求这 N 头牛的最短路径（一个来回）中最长的一条的长度。
特别提醒：可能有权值不同的重边。 -
思路
最短路径(一个来回)并不是路程*2,而是求正反路径权值之和
多对一的最短路≡反向建图一对多的最短路 -
代码
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
44from collections import deque
from copy import deepcopy
N = 1010
INF = int(1e10)
g = [[] for _ in range(N)]
dist, st = [INF] * N, [0] * N
def spfa(u):
q = deque()
q.appendleft(u)
st[u] = 1
dist[u] = 0
while q:
u = q.pop()
st[u] = 0
for v, w in g[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
if st[v] == 0:
st[v] = 1
q.appendleft(v)
n, m, s = map(int, input().split())
record = []
for i in range(m):
u, v, w = map(int, input().split())
record.append([u, v, w])
g[u].append([v, w])
spfa(s)
dist1 = deepcopy(dist)
g = [[] for _ in range(N)]
dist, st = [INF] * N, [0] * N
for i in range(m):
v, u, w = record[i]
g[u].append([v, w])
spfa(s)
ans = 0
for i in range(1, n + 1):
ans = max(ans, dist[i] + dist1[i])
print(ans)