백준 1504번 특정한 최단 경로

문제 링크입니다: https://www.acmicpc.net/problem/1504

V1과 V2를 꼭 지나야하므로 아래와 같은 두 가지 경우를 고려해야합니다.

1. 1 -> V1 -> V2 -> N

2. 1 -> V2 -> V1 -> N

따라서, 다익스트라 알고리즘을 1, V1, V2에 대해 전부 수행한 뒤 1번과 2번 중 최소인 경우를 출력합니다.

또한, 경로가 존재하지 않는 경우 -1을 출력해야하는데 987654321을 3번 더해주면 int 오버플로우가 발생하므로 answer가 INF 이상이거나 0 미만일 때 -1을 출력하도록 처리해줘야합니다.

#include <iostream>

#include <vector>

#include <queue>

#include <stack>

#include <functional>

#include <algorithm>

using namespace std;

 

const int MAX = 800 + 1;

const int INF = 987654321;

 

int N, M;

int trace[MAX]; //경로 파악 위해

vector<pair<int, int>> graph[MAX];

 

vector<int> dijkstra(int start, int vertex)

{

        vector<int> distance(vertex, INF);

        distance[start] = 0;

 

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

        pq.push({ 0, start });

 

        while (!pq.empty())

        {

                 int cost = pq.top().first;

                 int cur = pq.top().second;

                 pq.pop();

 

                 if (distance[cur] < cost)

                         continue;

 

                 for (int i = 0; i < graph[cur].size(); i++)

                 {

                         int neighbor = graph[cur][i].first;

                         int neighborDistance = cost + graph[cur][i].second;

 

                         //업데이트할 때마다 trace도 업데이트

                         if (distance[neighbor] > neighborDistance)

                         {

                                 distance[neighbor] = neighborDistance;

                                 trace[neighbor] = cur;

                                 pq.push({ neighborDistance, neighbor });

                         }

                 }

        }

        return distance;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> M;

 

        N++;

 

        for (int i = 0; i < M; i++)

        {

                 int u, v, w;

                 cin >> u >> v >> w;

 

                 //양방향

                 graph[u].push_back({ v, w });

                 graph[v].push_back({ u, w });

        }

       

        int node1, node2;

        cin >> node1 >> node2;

 

        vector<int> result = dijkstra(1, N);

        vector<int> temp1 = dijkstra(node1, N);

        vector<int> temp2 = dijkstra(node2, N);

        //두 가지 경우

        //1. 1 -> node1 -> node2 -> N

        //2. 1 -> node2 -> node1 -> N

        int answer = min({ result[node1] + temp1[node2] + temp2[N - 1], result[node2] + temp2[node1] + temp1[N - 1] });

        if (answer >= INF || answer < 0)

                 cout << -1 << "\n";

        else

                 cout << answer << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~