(2024-11-07) 5 문제 : 백준 - 9370 (미확인 도착지)

 

다익스트라 문제이다. 다만, 최단거리 중에서도 특정 간선을 지나는지 아닌지를 판별해야 하기 때문에 다소 까다로울 수 있는 문제이다.

 

그냥 다익스트라를 통해 하나의 경로만 구해버리면 최단거리가 동일한 다른 경로를 무시할 수 있기 때문에 다익스트라를 여러번 돌려서 간선을 반드시 지나는 최단거리를 구해주어야 한다. 

 

먼저, 본인은 시작노드를 기준으로 다익스트라 최단거리를 구하고, 냄새를 맡은 간선의 양 끝점을 기준으로도 다익스트라 최단거리를 구했다. 이렇게 하면 다익스트라를 이용해 구한 최단거리 배열은 총 3개가 있다.

 

이 3개의 최단거리를 이용해 시작점 -> 간선의 왼쪽점 -> 간선의 오른쪽점 경로의 최단 거리를 구할 수 있다.

간선의 양 끝점중 어느 쪽을 먼저 가느냐에 따라 최단거리가 달라질 수 있으므로 시작점 -> 간선의 오른쪽점 -> 간선의왼쪽점도 확인해준다.

 

이 둘중 더 작은 최단거리의 값이 시작지점을 기준으로 구한 다익스트라 최단거리 배열에서 도착 노드를 향한 최단거리와 같다면 냄새를 맡은 경로를 포함한 최단거리 경로가 존재한다는 의미이므로 정답 배열에 넣어주면 된다.

 

마지막으로 오름차순으로 출력해야 하므로 정답배열을 정렬해주면 된다.

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

std::vector<int> Dijk(int _StartNode, const std::vector<std::vector<std::pair<int, int>>>& _Link)
{
    std::vector<int> MinCost(_Link.size(), 100000000);

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> PQ;
    PQ.push({ 0, _StartNode });
    MinCost[_StartNode] = 0;

    while (PQ.size() > 0)
    {
        auto [CurCost, CurNode] = PQ.top();
        PQ.pop();

        for (int i = 0; i < _Link[CurNode].size(); i++)
        {
            int NextNode = _Link[CurNode][i].first;
            int NextCost = _Link[CurNode][i].second + CurCost;

            if (NextCost < MinCost[NextNode])
            {
                MinCost[NextNode] = NextCost;
                PQ.push({ NextCost, NextNode });
            }
        }
    }

    return MinCost;
}

int main()
{
    Init();

    int NumCase = 0;
    std::cin >> NumCase;

    for (int Case = 0; Case < NumCase; Case++)
    {
        int NumNode = 0, NumEdge = 0, NumEndNode = 0;
        std::cin >> NumNode >> NumEdge >> NumEndNode;

        int StartNode = 0;
        std::pair<int, int> FindedEdge;

        std::cin >> StartNode >> FindedEdge.first >> FindedEdge.second;
        StartNode--, FindedEdge.first--, FindedEdge.second--;

        std::vector<std::vector<std::pair<int, int>>> Link(NumNode);
        for (int i = 0; i < NumEdge; i++)
        {
            int Start = 0, End = 0, Cost = 0;
            std::cin >> Start >> End >> Cost;

            Link[Start - 1].push_back({ End - 1, Cost });
            Link[End - 1].push_back({ Start - 1, Cost });
        }

        std::vector<int> EndNodes(NumEndNode);
        for (int i = 0; i < NumEndNode; i++)
        {
            std::cin >> EndNodes[i];
            EndNodes[i]--;
        }

        std::vector<int> MinCostFromStart = Dijk(StartNode, Link);
        std::vector<int> MinCostFromEdgeF = Dijk(FindedEdge.first, Link);
        std::vector<int> MinCostFromEdgeS = Dijk(FindedEdge.second, Link);
    
        std::vector<int> Answer;
        Answer.reserve(EndNodes.size());

        for (int i = 0; i < EndNodes.size(); i++)
        {
            int CurNode = EndNodes[i];

            int MinCost_1 = MinCostFromStart[CurNode];
            
            int MinCost_2 = MinCostFromStart[FindedEdge.first] + MinCostFromEdgeF[FindedEdge.second] + MinCostFromEdgeS[CurNode];
            int MinCost_3 = MinCostFromStart[FindedEdge.second] + MinCostFromEdgeS[FindedEdge.first] + MinCostFromEdgeF[CurNode];

            if (MinCost_1 == std::min(MinCost_2, MinCost_3))
            {
                Answer.push_back(CurNode);
            }
        }

        std::sort(Answer.begin(), Answer.end());
        for (int AnswerNode : Answer)
        {
            std::cout << AnswerNode + 1 << " ";
        }

        std::cout << "\n";
    }


    return 0;
}