Прикреплённый файл «floyd-warshell.py»
Загрузка 1 #!/usr/bin/env python
2 # coding: utf
3 '''
4 Дана таблица, содержащая стоимость проезда из города i в город k по N г
5 ородам (необязательно симметричная). Проезд стоит от 1 до 1000р, если проезда не
6 т, в таблице записано N**2*1000. Вводятся два номера городов -- A и B. Вычислить
7 минимальную стоимость проезда из A в B с учётом пересадок.
8
9 Ввод:
10 N
11 1-я строка таблицы из N элементов (через пробел)
12 ...
13 N-я строка таблицы из N элементов (через пробел)
14 A
15 B
16
17 Вывод:
18 Минимальная стоимость или "NO" в случае недоступности
19 '''
20
21 import sys,random
22
23 def shortgen(N,A,B):
24 Max=N**2*1000
25 return [ [ i!=j and (random.randrange(5) and random.randint(1,1000) or Max) or 0 for j in xrange(N) ] for i in xrange(N) ]
26
27 def accugen(N,A,B):
28 Max=N**2*1000
29 T=[[0]*N for i in xrange(N)]
30 for i in xrange(N):
31 for j in xrange(N):
32 if i==j: continue # путь из i в i
33 v=random.randint(1,1000)
34 if (i!=A or j!=B) and not random.randrange(6): # короткий путь в обход
35 v=1
36 if random.randrange(4): # недоступно
37 v=Max
38 T[i][j]=v
39 return T
40
41 def floyd(T,N,A,B):
42 Next=True
43 while Next:
44 Next=False
45 for i in xrange(N):
46 for j in xrange(N):
47 for k in xrange(N):
48 if T[i][k]+T[k][j]<T[i][j]:
49 T[i][j]=T[i][k]+T[k][j]
50 Next=True
51
52
53 if len(sys.argv) > 1: # Генератор
54 N=int(sys.argv[1])
55 A,B=random.sample(xrange(N),2)
56 print N
57 for l in accugen(N,A,B):
58 print " ".join(str(c) for c in l)
59 print A, B
60 else: # Решение
61 N=input()
62 T=[]
63 for i in xrange(N):
64 T.append([int(s) for s in raw_input().split()])
65 A,B=[int(s) for s in raw_input().split()]
66
67 old=T[A][B]
68 floyd(T,N,A,B)
69 print old, (T[A][B]>=N**2*1000) and "NO" or T[A][B]
Прикреплённые файлы
Для ссылки на прикреплённый файл в тексте страницы напишите attachment:имяфайла, как показано ниже в списке файлов. Не используйте URL из ссылки «[получить]», так как он чисто внутренний и может измениться.- [получить | показать] (2011-12-14 16:25:52, 1.0 KB) [[attachment:Avyshlovlab.py]]
- [получить | показать] (2011-12-14 13:37:48, 2.2 KB) [[attachment:floyd-warshell.py]]
- [получить | показать] (2011-12-14 13:39:03, 1.3 KB) [[attachment:labdijkstra.py]]
- [получить | показать] (2011-12-14 13:39:59, 0.8 KB) [[attachment:labpur.py]]
- [получить | показать] (2011-12-13 22:42:54, 2.2 KB) [[attachment:ray_lab.py]]
Вам нельзя прикреплять файлы к этой странице.