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]
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 5 Years Ago by Gribouillis: n/a

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 article has been dead for over six months. Start a new discussion instead.