задача 7

 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
n=int(input())
p=[int(s) for s in input().split()]
m=int(input())
b=[[0] * n for i in range(n)]
for i in range(m):
a=[int(s) for s in input().split()]
b[a[0]-1][a[1]-1]=p[a[0]-1]
b[a[1]-1][a[0]-1]=p[a[1]-1]
s,f=1,n
c,d,e,visited=[100*100]*n,10000,s-1,[False]*n
c[s-1]=0
visited[s-1]=True
for i in range(n):
if b[s-1][i]>0:
c[i]=b[s-1][i]
for j in range(n):
for i in range(n):
if c[i]<d and c[i]>0 and i!=e and not visited[i]:
d=c[i]
e=i
for k in range(n):
if b[e][k]>0 and c[e]+b[e][k]<c[k]:
c[k]=c[e]+b[e][k]
visited[e]=True
d=10000
if c[f-1]<10000:
print(c[f-1])
else:
print(-1)