[백준/C++] 1504 특정한 최단 경로

1504 특정한 최단 경로

#include <bits/stdc++.h>
using namespace std;

int INF = 98765432;
vector<pair<int, int>> vec[802];
int dist[803];
void bfs(int a)
{
    memset(dist, INF, sizeof(dist));
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> queue;
    queue.push(make_pair(0, a));
    dist[a] = 0;
    while (!queue.empty())
    {
        int sum_distance = queue.top().first;
        int x = queue.top().second;
        queue.pop();
        
        if (dist[x] < sum_distance)
            continue;
        for (int i = 0; i<vec[x].size(); ++i)
        {
            int nx = vec[x][i].first;
            int ncost = sum_distance + vec[x][i].second;
            if (dist[nx] > ncost)
            {
                queue.push({ ncost,nx });
                dist[nx] = ncost;
            }
        }
    }
}

int compare_ab(int a, int b)
{
    if (a < b)
        return a;
    else
        return b;
}

int main() 
{
    int node, edge, result;
    cin >> node >> edge;
    for (int i = 0; i < edge; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        vec[a].push_back({ b,c });
        vec[b].push_back({ a,c });
    }
    int dest1, dest2;
    cin >> dest1 >> dest2;
    
    bfs(1);
    int to_dest1 = dist[dest1];
    int to_dest2 = dist[dest2];

    bfs(dest1);
    int dest1_to_dest2 = dist[dest2];
    int dest1_to_node = dist[node];

    bfs(dest2);
    int dest2_to_node = dist[node];

    result = compare_ab(INF, to_dest1 + dest1_to_dest2 + dest2_to_node);
    result = compare_ab(result, to_dest2 + dest1_to_dest2 + dest1_to_node);
    if (result >= INF)
        cout << -1;
    else
        cout << result;

}

• 다익스트라를 활용해서 푸는 문제이다.
• 다익스트라를 이용해서 무조건 거쳐야하는 정점까지 최단 거리를 구하고, 다시 그 정점부터 node정점까지 최단거리를 구해주면 쉽게 해결할 수 있다. 즉, 다익스트라를 3번 써야한다.
• a-b-c, b-a-c를 구해서 비교해 답을 제출해야 한다.