Dijkstra풀이 (백준 9370번)

Kang Joohan·2022년 1월 21일
0

algorithm/dijkstra

목록 보기
3/5

문제

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)

어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.

이 듀오는 대체 어디로 가고 있는 것일까?

예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 두 검은 원 중 하나로 가고 있고 점선으로 표시된 도로에서 냄새를 맡았다. 따라서 그들은 6으로 향하고

입력

첫 번째 줄에는 테스트 케이스의 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스마다

  • 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다.
  • 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h)
  • 그 다음 m개의 각 줄마다 3개의 정수 a, b, d (1 ≤ a < b ≤ n and 1 ≤ d ≤ 1 000)가 주어진다. a와 b 사이에 길이 d의 양방향 도로가 있다는 뜻이다.
  • 그 다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. 이 t개의 지점들은 서로 다른 위치이며 모두 s와 같지 않다.

교차로 사이에는 도로가 많아봐야 1개이다. m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재한다. 또한 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.

출력

테스트 케이스마다

  • 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.

풀이방법

Dijkstra 알고리즘의 활용 문제이다. 우선, g -> h 교차로를 반드시 지나야 하므로 경로는,
Strat -> G -> H -> X(목적지) or Start -> H -> G -> X(목적지) 이 둘 중 하나가
Start -> X 로 바로 가는 최소거리의 경우와 같아야 한다. 이를 염두에 두고 Dijkstra 알고리즘을 작성해 나가면 될 것이다.

코드

#include <iostream>
#include <queue>
#include <algorithm>

#define MAX 2000 + 1
#define INF 987654321

using namespace std;

int n, m, t; //교차로 도로 목적지
int s, g, h; //예술가 출발지, g와 h 사이에 있는 도로를 지나가야함.

int StoG, StoH, GtoH, GtoX, HtoX, StoX;

int dist[MAX];

//알고리즘 정리
//우선 Dijkstra 알고리즘을 짜고 난 후, 교차로 gh를 반드시 지나면서 최단거리 이동을 만족한다면 출력해주는것을 목표로한다.
// Dijkstra로 Start -> g -> h를 지나가며 최단거리를 만족하는지 판단해주는 Dijkstra를 짜주면 된다.

void Dijkstra(int start, vector<pair<int,int>> A[])
{
    for (int i = 0; i <= n; ++i)
    {
        dist[i] = INF; //모든 정점들까지의 가중치들을 초기화 해준다.
    }

    // first 도착하기까지의 가중치, second : 현재 정점
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    dist[start] = 0;

    while (!pq.empty())
    {
        int idx = pq.top().second;
        int cost = pq.top().first;
        pq.pop();

        for (int i = 0; i < A[idx].size(); ++i)
        {
            int Next = A[idx][i].first;
            int Ncost = A[idx][i].second + cost; //다음 정점까지의 가중치 값
            if (dist[Next] > Ncost)
            {
                dist[Next] = Ncost;
                pq.push({dist[Next], Next});
            }
        }
    }
}

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


// s -> g -> h -> x or s -> h -> g - > x가 s -> x보다 거리가 짧다면 vector<int> goal에 넣어준다. 그 후, goal을 다 뽑아준다.
int main()
{
    Init();

    vector<int> goal;
    int x[100];

    int test;
    cin >> test;

    while (test--)
    {
        
        cin >> n >> m >> t;
        cin >> s >> g >> h;

        vector<pair<int,int>> V[n + 1];

        for (int i = 0; i < m; ++i)
        {
            int a, b, d; // from, to, 가중치
            cin >> a >> b >> d;
            V[a].push_back({b, d});
            V[b].push_back({a, d});
            //연결된 도로들과 가중치 입력
        }

        for (int i = 0; i < t; ++i)
        {
            cin >> x[i];
        }

        for (int i = 0; i < t; ++i)
        {
            Dijkstra(s,V);
            StoG = dist[g];
            StoH = dist[h];
            StoX = dist[x[i]];
            // S ~ G 거리 S ~ H 거리
            Dijkstra(g,V);
            GtoH = dist[h];
            GtoX = dist[x[i]];
            // G ~ H 거리 G ~ X 거리
            Dijkstra(h,V);
            HtoX = dist[x[i]];
            // H ~ X 거리

            // S -> G -> H -> X or S -> H -> G -> X 거리가 S -> X거리보다 짧다면 vector goal에 넣어주자.
            if (StoX == (StoG + GtoH + HtoX) || StoX == (StoH + GtoH + GtoX))
            {
                goal.push_back(x[i]);
            }
        }

        sort(goal.begin(), goal.end());

        for (int i = 0; i < goal.size(); ++i)
        {
            cout << goal[i] << " ";
        }

        goal.clear();

        cout << '\n';
    }

    return 0;
}
profile
be Gritty

0개의 댓글