백준 12834 (주간 미팅) - pypy

주간 미팅

 

문제

만약 KIST 기사단 2기로 여러분이 선발된다면, 서울 월곡에 있는 KIST와 양재에 있는 씨알푸드에서 팀이 함께 만나 의논하고 함께 작업할 시간을 가지게 된다. 누구나 그 회의 장소에 빨리 가고 싶은 마음은 똑같을 것이다.

각 장소를 노드로 생각하고, 연결된 도로를 간선으로 생각하면 그래프를 구성할 수 있다. KIST 기사단 N명의 집이 있는 노드 번호와 KIST, 씨알푸드의 노드 번호가 주어지고, 한 사람의 거리 di = (집-KIST의 최단 거리) + (집-씨알푸드의 최단 거리)로 정의된다. 단, 도달할 수 없는 경우의 최단 거리는 -1로 정의한다. 예를 들어, 어떤 사람이 KIST로는 갈 수 없고 씨알푸드까지의 최단 거리가 10인 경우 이 사람의 거리 d는 9이고, 다른 사람이 KIST, 씨알푸드로 모두 갈 수 없을 경우 이 사람의 거리 d는 -2이다. 이때 Σdi의 값을 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 KIST 기사단 팀원의 수 N, 장소의 수 V, 도로의 수 E가 주어진다. (N ≤ 100, V ≤ 1000, E ≤ 10000)

둘째 줄에 KIST의 위치 A와 씨알푸드의 위치 B가 주어진다. (1 ≤ A, B ≤ V)

셋째 줄에 팀원 N명의 집의 위치 Hi가 공백을 사이에 두고 주어진다. (1 ≤ i ≤ N, 1 ≤ Hi ≤ V)

넷째 줄부터 E+3번째 줄까지는 도로의 양 끝 장소 a, b와 길이 l이 주어진다. (1 ≤ a, b ≤ V, 1 ≤ l ≤ 100)

 

출력

모든 사람의 최단 거리의 합을 출력한다. 단, KIST나 씨알푸드로 갈 수 없는 경우에는 -1로 처리한다.

---

다익스트라 방식을 쓰는 문제였다.

오랜만에 다익스트라를 풀어서 까먹어서 다시 찾아봤다.

한 장소에서 특정 장소들까지의 거리라 다익스트라로 생각하였고 A, B 두 장소의 최단거리를 구하였다.

그러나 python으로는 시간 초과가 났다.

그래서 pypy로 해결

'''
주간 미팅

'''
from sys import stdin
input = stdin.readline

N, V, E = map(int,input().split())
A, B = map(int,input().split())
H = list(map(int,input().split()))

INF = 987654321

maps = [[0] * (V+1) for _ in range(V+1)]

for _ in range(E):
    a, b, l = map(int,input().split())

    maps[a][b] = l
    maps[b][a] = l

# 다익스트라
def dij(st):
    global total
    D = [INF] * (V+1)
    D[st] = 0
    visit = [0] * (V+1)

    for i in range(1,V+1):
        if visit[A] and visit[B]:
            break
        min_v = INF
        for j in range(1,V+1):
            if visit[j] == 0 and min_v > D[j]:
                u = j
                min_v = D[j]

        visit[u] = 1

        for v in range(1,V+1):
            if D[v] > D[u] + maps[u][v] and maps[u][v] and visit[v] == 0:
                D[v] = D[u] + maps[u][v]
    # 거리 구하기
    if D[A] == INF:
        D[A] = -1
    if D[B] == INF:
        D[B] = -1

    total += D[A] + D[B]

total = 0

for i in H:
    dij(i)

print(total)