4241. 货物运输
摘要
Title: 4241. 货物运输
Tag: 最短路模型、spfa
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
4241. 货物运输
-
题意
给定一个 n 个点 m 条边的无重边无自环的无向图。
点的编号为 1∼n。
现在，要从点 1 到点 n 运货。
已知每条边的最大承重，请你计算一次最多可以运多少货物。 -
思路
求最短边的最大值，和上题的青蛙相反
当边长度小的时候，就松弛，赋予更大的值注意初始化，从点开始，那么就是无穷大开始
-
代码
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'''
Author: NEFU AB-IN
Date: 2022-04-16 11:08:47
FilePath: \ACM\Acwing\4241.py
LastEditTime: 2022-04-16 11:08:48
'''
from collections import deque
N = 1010
INF = int(1e9)
g = [[0] * N for _ in range(N)]
dist, st = [0] * N, [0] * N
def spfa(u):
q = deque()
q.appendleft(u)
st[u] = 1
dist[u] = INF
while q:
u = q.pop()
st[u] = 0
for v in range(1, n + 1):
if dist[v] < min(dist[u], g[u][v]):
dist[v] = min(dist[u], g[u][v])
if st[v] == 0:
st[v] = 1
q.appendleft(v)
return dist[n]
for _ in range(1, int(input()) + 1):
dist, st = [0] * N, [0] * N
g = [[0] * N for _ in range(N)]
n, m = map(int, input().split())
for i in range(m):
u, v, w = map(int, input().split())
g[u][v] = w
g[v][u] = w
print(f"Scenario #{_}:")
print(spfa(1))
print()