[Algorithm]Baekjoon 9370번 : 미확인 도착지

https://www.acmicpc.net/problem/9370

9370번: 미확인 도착지

struct Node
{
    int node;
    int weight;
};
 
struct cmp
{
    bool operator() (const Node& a, const Node& b)
    {
        return a.weight < b.weight;
    }
};
 
int T, n, m, t, s, g, h, a, b, d, x;
vector<vector<Node>> graph(2001);
vector<int> dests;
int dists[2][2001];
vector<int> answers[100];
 
void dij(int start, int flag)
{
    dists[flag][start] = 0;
    priority_queue<Node, vector<Node>, cmp> pq;
    pq.push({ start,0 });
 
    while (!pq.empty())
    {
        int curNode = pq.top().node;
        int curWeight = pq.top().weight;
        pq.pop();
 
        if (dists[flag][curNode] < curWeight) continue;
 
        for (int i = 0; i < graph[curNode].size(); ++i)
        {
            int nextNode = graph[curNode][i].node;
            int nextWeight = graph[curNode][i].weight;
 
            if (dists[flag][curNode] + nextWeight < dists[flag][nextNode])
            {
                dists[flag][nextNode] = dists[flag][curNode] + nextWeight;
                pq.push({ nextNode,dists[flag][nextNode] });
            }
        }
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> T;
 
    for (int i = 0; i < T; ++i)
    {
        cin >> n >> m >> t >> s >> g >> h;
 
        memset(dists, 0x3f, sizeof(dists));
        vector<vector<Node>> temp(2001);
        graph = temp;
        dests.clear();
        int smellCost = 0;
 
        for (int j = 0; j < m; ++j)
        {
            cin >> a >> b >> d;
 
            graph[a].push_back({ b,d });
            graph[b].push_back({ a,d });
 
            if ((a == g && b == h) || (a == h && b == g)) smellCost = d;
        }
 
        for (int k = 0; k < t; ++k)
        {
            cin >> x;
            dests.push_back(x);
        }
        
        dij(s, 0);
 
        int adjDest1 = dists[0][g] < dists[0][h] ? g : h;
        int adjDest2 = dists[0][h] > dists[0][g] ? h : g;
 
        dij(adjDest2, 1);
 
        sort(dests.begin(), dests.end());
        for (int j = 0; j < dests.size(); ++j)
        {
            int dest = dests[j];
 
            if (dists[0][adjDest1] + smellCost + dists[1][dest] == dists[0][dest])
            {
                answers[i].push_back(dest);
            }
        }
    }
 
    for (int i = 0; i < T; ++i)
    {
        for (int j = 0; j < answers[i].size(); ++j)
        {
            printf("%d ", answers[i][j]);
        }
        printf("\n");
    }
}

풀이 방법은 의외로 쉽게 생각하긴 했다.

이 문제에서 중요한 점은 특정 간선이 도착지후보에 포함이 되어있느냐? 안되어있느냐를 알아야하는 문제이다.

그렇기 때문에 반드시 g->h 이동이라던가 h->g 이동이 반드시 포함되어 있어야 한다.

 

그래서 처음에는 매 테스트케이스마다 다익스트라를 3번 돌렸었는데, 통과는 했다. 근데 생각보다 다른사람풀이에 비해 시간이 좀 길게나와서 참고해봤는데 2번으로도 충분히 가능하단걸 깨달았다.

출발지에서 한번, 그리고 g와 h중 출발지에서 더 먼 걸로 한번 -> 총 2번.

처음에 인풋으로 g <-> h의 코스트를 알려주기 때문에 3번할필요가 없었다.

 

그래서

"출발지->G or H(더 가까운거)의 최단거리" + "G <-> H 코스트" + "G or H(더 먼거) -> 목적지의 최단거리 " 의 값이, 출발지에서부터 목적지후보까지의 최단거리값과 같다면 해당 목적지후보에는 냄새나는 간선이 포함된다고 판단하고 정답을 카운팅해주면 된다.