모비스터디 (백준 31230)

안녕하세요. 오늘은 최단경로를 찾아볼 거예요.

문제

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

아이디어

진짜로 모든 경로를 다 찾아서... 그 위에 있는 정점들의 개수를 세는건... 좀... 아닙니다..
A-B의 거리를 x라고 했을 때 C가 최단경로 위에 있으려면 A-C-B의 거리가 x가 되면 됩니다. 당연하지만 x 미만일 수는 없습니다. 이때 굳이 A-B의 거리를 구할 필요는 없는게 A-C-B의 거리가 최소가 되는 값 x는 당연히 A-B의 거리이기 때문입니다.

소스코드

#include <iostream>
#include <vector>
#include <queue>
#define ll long long
using namespace std;

vector <pair <ll, ll> > graph[202020];
ll dp[202020][2] = { 0 }, N;

void dij(ll node, ll idx)
{
    priority_queue <pair <ll, ll>, vector <pair <ll, ll> >, greater<> > pq;
    ll now, dis, cur, curdis;
    for (ll i = 1; i <= N; i++) dp[i][idx] = 3e15;
    dp[node][idx] = 0; pq.push({ 0,node });

    while (pq.size())
    {
        now = pq.top().second;
        dis = pq.top().first;
        pq.pop();
        if (dp[now][idx] < dis) continue;
        for (pair <ll, ll> temp : graph[now])
        {
            cur = temp.first;
            curdis = dis + temp.second;
            if (dp[cur][idx] > curdis)
            {
                dp[cur][idx] = curdis;
                pq.push({ curdis,cur });
            }
        }
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll M, A, B, i, a, b, c;
    cin >> N >> M >> A >> B;
    for (i = 0; i < M; i++)
    {
        cin >> a >> b >> c;
        graph[a].push_back({ b,c });
        graph[b].push_back({ a,c });
    }
    dij(A, 0); dij(B, 1);

    ll mn = 1e18;
    for (i = 1; i <= N; i++)
        mn = min(mn, dp[i][0] + dp[i][1]);

    vector <ll> Ans;
    for (i = 1; i <= N; i++)
        if (dp[i][0] + dp[i][1] == mn)
            Ans.push_back(i);

    cout << Ans.size() << "\n";
    for (ll x : Ans)
        cout << x << ' ';
}

감사합니다.