Прикреплённый файл «2013-02-15.trip.py»
Загрузка 1 #!/usr/bin/env python
2 # coding: utf
3 '''
4 Таблица N×N содержит стоимости прямого проезда из города i в город j (i<N, j<N, i≠j). Стоимость проезда не превышает S, если из города i в город j проезда нет, в таблице стоит S*N.
5
6 Определить минимальную стоимость проезда из города A в город B с учётом возможных пересадок
7 …вывести также любой маршрут из A в B с минимальной стоимостью проезда
8 составить таблицу минимальной стоимости проезда из любого города в любой
9 '''
10
11 import sys, itertools, copy
12
13 if len(sys.argv)>1:
14 # Генератор
15 from random import randrange, sample
16 N=int(sys.argv[1])
17 Proc=len(sys.argv)>2 and int(sys.argv[2]) or 30
18 S=100
19 L=sample([(i,j) for i in xrange(N) for j in xrange(N) if i!=j], N*N*Proc/100)
20 M=[[(i,j) in L and randrange(1,S) or S*N*N for i in xrange(N)] for j in xrange(N)]
21 print M
22 sys.exit(0)
23
24 def Floyd(Map):
25 '''Метод Флойда'''
26 Next=True
27 while Next:
28 Next=False
29 for i in xrange(len(Map)):
30 for j in xrange(len(Map)):
31 for k in xrange(len(Map)):
32 if i!=k and j!=k and Map[i][j]>Map[i][k]+Map[k][j]:
33 # Есть такой научный термин: релаксация связи
34 Next=True
35 Map[i][j]=Map[i][k]+Map[k][j]
36
37
38 def Dijkstra(Map,s):
39 '''Метод Дейкстры'''
40 def get1(e): return e[1][1]
41 # Пока из города s никуда не доехать
42 Next=[[i,MAX] for i in xrange(len(Map))]
43 # …кроме самого s, что бесплатно
44 Next[s]=[s,0]
45 Res=[]
46 # Для каждого города
47 while Next:
48 # Выберем такой город s, к которому дешевле ехать
49 i,(s,w)=min(enumerate(Next),key=get1)
50 Res.append(Next.pop(i))
51 # Для всех оставшихся городов
52 for i,(town,way) in enumerate(Next):
53 if Map[s][town]<MAX:
54 # Проверим, не дешевле ли доехать до них через s
55 if way>w+Map[s][town]:
56 Next[i]=[town,w+Map[s][town]]
57 return zip(*sorted(Res))[1]
58
59 def prinTab(Map,w=4):
60 print "_"*len(Map)*w
61 print "\n".join(" ".join(("{0:"+str(w-1)+"}").format(c==MAX and " # " or c) for c in l) for l in Map)
62
63 Inp=input()
64 MAX=max(itertools.chain(*Inp))
65 prinTab(Inp)
66
67 Map=copy.deepcopy(Inp)
68 print "_"*len(Map)*4
69 print " ".join("{0:3}".format(c) for c in Dijkstra(Map,0))
70 Floyd(Map)
71 prinTab(Map)
Прикреплённые файлы
Для ссылки на прикреплённый файл в тексте страницы напишите attachment:имяфайла, как показано ниже в списке файлов. Не используйте URL из ссылки «[получить]», так как он чисто внутренний и может измениться.Вам нельзя прикреплять файлы к этой странице.