[Python][BOJ 6951] Packet Routing

 

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

6951번: Packet Routing

 

 엄청 쉬운 Floyd-warshall 문제이다. n개의 정점에 w개의 간선정보을 받고 계산 후 p개의 질문에 대답하면 되는 문제이다. 그냥 값 받고 양방향으로 가중치를 저장하고 플로이드 돌리고 저장되어 잇는 질문값의 최소거리를 출력하면 AC를 받는다.

 

코드는 아래에 있다.

import sys
input=sys.stdin.readline

n,w,p=map(int,input().split())

d=[[1e9 for _ in range(n+1)]for _ in range(n+1)]

def floid():
    for k in range(n+1):
        for i in range(n+1):
            for j in range(n+1):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])

for _ in range(w):
    x,y,z=map(int,input().split())
    d[x][y]=z
    d[y][x]=z

floid()

for _ in range(p):
    x,y=map(int,input().split())
    print(d[x][y])