백준 1504(특정한 최단 경로) - 해결(참고)

특정한 최단 경로

 

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)

 

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

---

처음 생각한 방식은 다익스트라를 여러번 하는 것

처음에는 4가지 경로를 생각하였다 1 - v1 - v2 - N / 1 - v1 - v2 - v1 - N / 1 - v2 - v1 - N / 1 - v2 - v1 - v2 - N

하지만 2, 4번 같은 경우 할 필요가 없다는 것을 알게되었고 하면 더 크게 나온다고  생각이 되었다.

그래서 총 2가지 경로 1 - v1 - v2 - N /1 - v2 - v1 - N 를 생각하였고 

각각을 다익스트라로 탐색하기로 하였다.

하지만 Typeerror가 났는데 이유는 -1을 신경을 쓰지 않아서 그래서 추가하였는데 

None으로 나오는걸 사용하였으나 이렇게 하면 안된다는걸 알아서(0을 and 했을 때 못넘어가기 때문에)

-1로 출력을하였다.

그리고 v1 == 1, v2 == N인 경우를 신경 쓰지않아 틀리기도 하였다.

import sys
input = sys.stdin.readline

N, E = map(int,input().split())
# map은 인접 리스트로
maps = [[] for _ in range(N+1)]

# 맵 만들기
for _ in range(E):
    a, b, c = map(int,input().split())
    maps[a].append((b,c))
    maps[b].append((a,c))

INF = 987654321
# 다익스트라 st -> ed
def dij(st,ed):
    dist = [INF] * (N+1)
    visit = [0] * (N+1)
    dist[st] = 0

    for _ in range(N):
        min_d = INF
        for i in range(1,N+1):
            if min_d > dist[i] and visit[i] == 0:
                u = i
                min_d = dist[i]
    
        visit[u] = 1
        if u == ed:
            return dist[u]

        for b, c in maps[u]:
            if dist[b] > dist[u] + c:
                dist[b] = dist[u] + c
    # 못가면 -1
    return -1


v1, v2 = map(int,input().split())
# 통과 못하면 -1을 출력하기 위해
route = -1

# 각 경로가 가지 못하면 안되기 때문에 0 이상 이면 된다
# 거리가 0일수도 있기 때문
if dij(1,v1) >= 0 and dij(v1,v2) >= 0 and dij(v2,N) >= 0 and dij(1,v2) >= 0 and dij(v1,N) >= 0:
    # 두개의 경로중 가장 짧은 것 - 경로는 v1으로 먼저 오는 것과 v2로 먼저 오는 경우를 나누어서
    route1 = dij(1,v1) + dij(v1,v2) + dij(v2,N)
    route2 = dij(1,v2) + dij(v1,v2) + dij(v1,N)
    route = min(route1,route2)
print(route)

예시

4 4

1 2 1

2 3 4

2 4 5

3 4 100

2 3

출력 : 14

 

4 5

1 2 100

2 3 4

2 4 5

3 4 100

1 3 1

2 3

출력 : 10

 

7 7

1 2 3

3 2 5

1 3 1

6 5 3

7 5 8

5 4 2

6 4 3

2 6

출력 : -1

 

4 6

1 2 3

2 3 3

3 4 1

1 3 5

2 4 5

1 4 4

1 4

출력 : 4

 

3 3

1 3 20

1 2 15

2 3 6

1 3

출력 : 20