Level 3. 부대복귀

Level 3. 부대복귀

 

 

전형적인 다익스트라 문제이다.

• 특정 지점에서 다른 지점까지의 최단 거리를 구할 때, 다익스트라를 사용한다.
• 이때 음수 가중치가 존재한다면, 벨만-포드를 사용한다.
  벨만-포드는 음수 사이클을 확인할 때도 사용한다.
• 모든 지점 간의 최단 거리를 구할 때는 플로이드-워셜을 사용한다.
• 그 외에, 최소 신장 트리(MST)를 구할 때는 크루스칼을 사용한다.

 

#include <iostream>
#include <vector>
#include <queue>

#define UNREACHABLE 200000

using namespace std;

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination)
{
    vector<int> answer;
    queue<int> que;
    vector<vector<int>> adj(n + 1);
    vector<int> distance(n + 1, UNREACHABLE);

    for (vector<int>& road : roads)
    {
        adj[road[0]].emplace_back(road[1]);
        adj[road[1]].emplace_back(road[0]);
    }

    distance[destination] = 0;
    que.emplace(destination);

    while (!que.empty())
    {
        int v = que.front(); que.pop();

        for (int vadj : adj[v])
        {
            int dist = distance[v] + 1;

            if (dist < distance[vadj])
            {
                distance[vadj] = dist;
                que.emplace(vadj);
            }
        }
    }

    for (int src : sources)
        if (distance[src] == UNREACHABLE)
            answer.emplace_back(-1);
        else
            answer.emplace_back(distance[src]);

    return answer;
}