0
from copy import deepcopy

sis = file("teedtest.01.sis", "r")
val = file("rp.val", "wt")

N, K = map(int, sis.readline().strip().split()) 

alist = []
for i in range(0, K):
  t = []
  for i in range(0, K):
    t.append(0)
  alist.append(t)
  
for i in range(K):
  a, b, c = map(int, sis.readline().strip().split())
  alist[a][b] = alist[b][a] = c

D = deepcopy(alist)
print D
for k in range(0, K): 
  for u in range(0, K): 
    for v in range(0, K): 
      #print k, u, v
      D[u][v] = min(D[u][v], (D[u][k] + D[k][v]))
      
for i in range(K):
  print D[i]
10 15
1 3 3
1 4 3
2 4 3
2 5 3
3 5 3
6 7 2
7 8 2
8 9 2
9 10 2
10 6 2
1 6 1
2 7 2
3 8 3
4 9 4
5 10 5

How to calculate all paths in every town to other?

Current output, it's not correct?

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
4
Contributors
5
Replies
6
Views
6 Years
Discussion Span
Last Post by pyTony
2
from copy import deepcopy

sis = file("teedtest.01.sis", "r")
val = file("rp.val", "wt")

N, K = map(int, sis.readline().strip().split()) 

alist = []
for i in range(0, K):
  t = []
  for i in range(0, K):
    t.append(0)
  alist.append(t)
  
for i in range(K):
  a, b, c = map(int, sis.readline().strip().split())
  alist[a][b] = alist[b][a] = c

D = deepcopy(alist)
print D
for k in range(0, K): 
  for u in range(0, K): 
    for v in range(0, K): 
      #print k, u, v
      D[u][v] = min(D[u][v], (D[u][k] + D[k][v]))
      
for i in range(K):
  print D[i]
10 15
1 3 3
1 4 3
2 4 3
2 5 3
3 5 3
6 7 2
7 8 2
8 9 2
9 10 2
10 6 2
1 6 1
2 7 2
3 8 3
4 9 4
5 10 5

How to calculate all paths in every town to other?

Current output, it's not correct?

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

The undefined values must be infinite. You should take all the coefficients initially equal to sys.maxint (or sys.maxsize in python 3).

Edited by Gribouillis: n/a

0

You can also work with floating point numbers and use float("inf") for the infinite value.

Thanks, it's works! and system.maxint seems too!

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.