[C++][백준 9370] 미확인 도착지

문제

접근 방법

문제가 설명이 불친절하다.
쉽게 말하자면 s에서 시작하여 g와 h를 거친 경우에도 최단 거리를 유지하느냐이다.

최단 거리이므로 다익스트라로 풀면 된다.
하지만 어떤 방식으로 푸느냐가 중요하다.

가장 빠르게 g-h를 도착한 다음 출구에서 목적지로 가면은 g-h를 거친 최단 거리일 것이다. 이 값이 시작 지점에서 바로 간 거리와 같은지 확인하면 된다.

코드

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
int tc, n, m, t, s, g, h, dist[2001][2], dest[101];
vector<pii> graph[2001];
priority_queue<pii, vector<pii>, greater<pii>> pq;
void findDist(int start, bool isSecond)
{
    dist[start][isSecond] = 0;
    pq.push({0, start});
    while (!pq.empty())
    {
        pii cur = pq.top();
        pq.pop();
        int curVal = cur.first;
        int curIdx = cur.second;
        for (pii next : graph[curIdx])
        {
            int nextIdx = next.first;
            int nextVal = next.second + curVal;
            if (dist[nextIdx][isSecond] <= nextVal)
                continue;
            dist[nextIdx][isSecond] = nextVal;
            pq.push({nextVal, nextIdx});
        }
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> tc;
    while (tc--)
    {
        memset(dist, 0x3f3f3f3f, sizeof(dist));
        for (int i = 1; i <= n; ++i)
            graph[i].clear();
        cin >> n >> m >> t >> s >> g >> h;
        for (int i = 0, a, b, d; i < m; ++i)
        {
            cin >> a >> b >> d;
            graph[a].push_back({b, d});
            graph[b].push_back({a, d});
        }
        for (int i = 0; i < t; ++i)
            cin >> dest[i];
        sort(dest, dest + t);
        findDist(s, false);
        int target, other, otherWayDist;
        if (dist[g][false] < dist[h][false])
            target = g, other = h;
        else
            target = h, other = g;
        otherWayDist = dist[target][false];
        for (pii next : graph[target])
            if (next.first == other)
            {
                otherWayDist += next.second;
                break;
            }
        findDist(other, true);
        for (int i = 0; i < t; ++i)
            if (dist[dest[i]][false] == otherWayDist + dist[dest[i]][true])
                cout << dest[i] << " ";
        cout << "\n";
    }
    return 0;
}

풀이

문제를 이해하는 데는 조금 시간이 걸렸지만, 이해한 뒤에 방법은 바로 알아냈다.
하지만 실수를 하나 했다.

for (int i = 1; i <= n; ++i)
            graph[i].clear();

이 부분에서 실수했다.
i=0; i<n으로 한 것이다.

그래서 자꾸 16퍼센트에서 틀렸고 원인을 모르니 조금씩 수정하다 많이 틀려버렸다.
처음부터 다시 적다가 알게 된 잘못이었다.

배열의 범위는 항상 조심해야 한다.