python最短路径_python 最短路径

贾格尔(Jagger)找到一张地图，该地图指示大量宝藏的位置，并希望找到它们。

该地图将几个位置标记为节点和几个边缘，这表示两个位置直接相连。 总共有n个节点和m个边。 贾格尔(Jagger)位于节点1，宝物位于节点n。

当他运行最短路径算法以找出通往宝藏的最短路径时，他突然发现除了他的起始节点和宝藏的位置以外，每个节点都有一个怪物。 节点u上的怪物具有力量su。 贾格尔的力量为x。 当且仅当x≥su时，Jagger才能通过节点u。

Jagger现在想知道最小x是多少，以便他可以找到从1到n的路径。

Jagger finds a map that indicates the location of a large number of

treasure and would like to find them.

The map marks several locations as nodes and several edges which indicates

that two locations are connected directly. There are n nodes and m edges in

total. Jagger is located at node 1 and the treasure is located at node n.

When he is running shortest path algorithm in his head to find out the

shortest path to the treasure, he suddenly finds out that every node has a

monster except his starting node and the location of the treasure. A monster at

node u has strength su. Jagger has strength x. Jagger can pass node u if and

only if x ≥ su.

Jagger is now wondering what’s the minimum x so that he can find a path

to from 1 to n.

Input

For this problem there are multiple test cases. The first line contains a single

integer T (1 ≤ T ≤ 100000) indicates the number of test cases. You are

suggested to write a loop to deal with different test cases.

Each test case consists of multiple lines. For each test case:

The first line contains two integer n(1 ≤ n ≤ 20000) and m(1 ≤ m ≤ 20000).

The second line contains n integer si(0 ≤ si≤ 106; s1 = 0; sn = 0) where si is

the strength of the monster at node i for 2 ≤ i ≤ n - 1.

Each of the next m lines contains two integers ui; vi(1 ≤ ui; vi≤ n) indicates that there is an edge between ui and vi.

Remark:

• The graph is connected for each testcase.

• It is guaranteed that the sum of all n among the test cases is smaller

than or equal to 105 and the sum of all m among the test cases is smaller

than or equal to 2 × 105.

• There may be multiple edges between same pair of nodes.

• There may be self-loop edges where two end of edge are same.

Output

Output minimum x so that there is path from 1 to n for Jagger.

Sample Input 1

2

2 1

0 0

1 2

4 4

0 50 100 0

1 2

1 3

2 4

3 4

Sample Output 1

0

50

Sample Input 2

4

6 12

0 6 7 4 10 0

6 4

1 3

3 6

5 3

1 2

2 2

6 2

1 6

1 3

6 5

1 4

1 4

7 8

0 8 7 7 3 3 0

7 3

3 5

1 5

5 2

3 5

6 7

4 7

1 6

6 13

0 7 3 4 9 0

3 1

2 4

6 1

5 6

5 1

4 2

3 1

6 1

1 4

1 2

3 6

3 6

3 5

10 9

0 6 7 8 5 5 8 8 4 0

8 4

6 8

8 5

1 2

6 9

8 2

10 9

3 8

7 3

Sample Output 2

0

3

0

8

思路：其实就是迪杰斯特拉的应用，只是稍微需要修改一下更新条件，即该点(u)能不能加入集合需要满足：x >= s[u]。

def djst(sour, cost, n, m, s, x):

distance = [99999999] + [cost[sour][i] for i in range(1, n+1)]

distance[sour] = 0

used = [False for _ in range(1+n)]

used[sour] = True

# print(distance)

max_x = max(s) + 1

# x = 8

# while x <= max_x:

while True:

v = -1

# 从未使用过的顶点中选择一个距离最小的顶点

for u in range(1, 1+n): # x >= s[u] and

if x >= s[u] and not used[u] and (v == -1 or distance[u] < distance[v]):

# print(u)

v = u

if v == -1:

break

# 将选定的顶点加入到S中, 同时进行距离更新

used[v] = True

# 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。

for u in range(1, 1+n):

if x >= s[u]:

distance[u] = min(distance[u], distance[v] + cost[v][u])

if distance[n] != 99999999:

return True

else:

return False

t = eval(input())

for i in range(t): # 样例数量

x = list(map(int, input().split()))

n, m = x[0], x[1] # 获取节点数量和边数

s = list(map(int, input().split())) # 读入怪物限制

cost = [[99999999] * (n+1) for i in range(n+1)] # 初始化每个点间的距离

for j in range(m): # 读边

temp = list(map(int, input().split()))

a, b = temp[0], temp[1]

# print(a, b)

cost[a][b] = cost[b][a] = 0

# print(cost)

s = [0] + s

max_x = max(s) + 1

for x in range(max_x+1):

r = djst(1, cost, n, m, s, x)

if r:

print(x)

break