[테스트케이스 추가] 백준 1719번: 택배 파이썬, python

1. 문제

https://www.acmicpc.net/problem/1719

1719번: 택배

 

 

2. 풀이

다익스트라

 

 

3. 구현

import sys
# sys.stdin = open('input.txt')
import math
import heapq

n,m = map(int, sys.stdin.readline().strip().split())

gph=[[] for _ in range(n+2)]
for i in range(m):
    s,e,w = map(int, sys.stdin.readline().strip().split())
    gph[s].append((e,w))
    gph[e].append((s,w))

total_dist=[]
total_path=[]
for i in range(1,n+1):
    dist=[math.inf for _ in range(n+2)]
    path=[-1 for _ in range(n+2)]
    edges=[]

    dist[i]=0
    heapq.heappush(edges, (dist[i],i))

    while edges:
        cost,pos = heapq.heappop(edges)
        if dist[pos]<cost:
            continue
        for p,c in gph[pos]:
            c+=cost
            if dist[p]>c:
                dist[p]=c
                heapq.heappush(edges,(c,p))
                path[p]=pos
    total_dist.append(dist)
    total_path.append(path)

# print(total_dist)
# print(total_path)

for i in range(1,n+1):
    for j in range(0,n):
        if i==j+1:
            sys.stdout.write('- ')
        else:
            sys.stdout.write(str(total_path[j][i])+' ')
    sys.stdout.write('\n')

 

 

 

4. 추가 테스트케이스

7 20
7 3 16 
4 2 12 
6 2 5 
6 1 9 
7 5 11 
2 1 13 
1 3 13 
7 2 8 
4 7 5 
3 7 7 
5 1 1 
4 1 7 
3 5 11 
5 7 5 
3 4 2 
7 1 18 
3 1 19 
2 5 15 
3 6 11 
1 7 15

답: 

- 2 4 4 5 6 5 
1 - 4 4 7 6 7 
4 4 - 4 4 6 7 
1 2 3 - 1 3 7 
1 7 1 1 - 1 7 
1 2 3 3 1 - 2 
5 2 3 4 5 2 -

 

 

5 10
1 5 9 
3 5 1 
5 2 7 
1 4 2 
2 5 2 
3 2 1 
2 3 3 
4 3 9 
3 1 1 
3 4 1

답:

- 3 3 4 3 
3 - 3 3 5 
1 2 - 4 5
1 3 3 - 3
3 2 3 3 -

 

10 40
7 3 3 
4 8 3 
10 1 11 
3 2 9 
10 3 5 
1 6 2 
2 1 8 
6 1 5 
5 3 4 
1 4 6 
1 5 13 
1 8 14 
8 7 7 
5 10 2 
3 8 13 
7 1 10 
7 6 14 
3 7 7 
10 2 15 
9 7 7 
7 10 7 
8 9 4 
2 5 8 
4 9 2 
3 5 12 
9 3 2 
5 1 13 
2 4 3 
3 4 15 
8 3 4 
7 5 6 
10 7 15 
2 7 2 
4 7 15 
4 2 9 
5 7 13 
1 7 14 
8 4 14 
1 2 2 
9 10 1

답:

- 2 2 2 2 6 2 2 2 2 
1 - 7 4 5 1 7 4 4 4 
7 7 - 9 5 7 7 8 9 9
2 2 9 - 9 2 2 8 9 9
2 2 3 10 - 2 7 10 10 10
1 1 1 1 1 - 1 1 1 1
2 2 3 2 5 2 - 8 3 3
4 4 3 4 9 4 7 - 9 9
4 4 3 4 10 4 3 8 - 10
9 9 9 9 5 9 9 9 9 -

 

 

 

@gcc 님 반례 ( https://www.acmicpc.net/board/view/44044 )

6 8
1 3 7
1 5 1
1 6 6
2 5 1
2 6 2
3 4 7
3 5 6
5 6 4

답:

- 5 3 3 5 5 
5 - 5 5 5 6 
1 5 - 4 5 5
3 3 3 - 3 3
1 2 3 3 - 2
2 2 2 2 2 -