[1504] 특정한 최단 경로

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

1504번: 특정한 최단 경로

방문하는 두 정점이 x, y라고 하면,

1 - x - y - n
1 - y - x - n

위 두 가지 경우만 체크하면 된다.

x나 y가 1, n인 경우도 나올 수 있지만, 예외처리를 할 필요는 없다.

 

입력이 연결그래프인지를 먼저 판별하면 -1을 출력해야 하는 경우를 배제하고 시작할수도 있겠다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

typedef struct {

    ll idx, cost;

} state;

constexpr ll MAX_N = 100000, INF = (ll)1e17;

ll n, m, s, e, dst[MAX_N + 1];

vector<state> adj[MAX_N + 1];

void dijkstra(ll s) {

    auto cmp = [&](state& A, state& B) -> bool { return A.cost > B.cost; };

    priority_queue<state, vector<state>, decltype(cmp)> q(cmp);

    q.push({s, 0});

    fill(dst, dst + MAX_N + 1, INF);

    dst[s] = 0;

    while (!q.empty()) {

        state cur = q.top();

        q.pop();

        if (cur.cost > dst[cur.idx]) continue;

        for (auto& nxt : adj[cur.idx]) {

            if (dst[nxt.idx] > dst[cur.idx] + nxt.cost) {

                dst[nxt.idx] = dst[cur.idx] + nxt.cost;

                q.push({nxt.idx, dst[nxt.idx]});

            }

        }

    }

    return;

}

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m;

    ll i;

    for (i = 0; i < m; i++) {

        ll A, B, C;

        cin >> A >> B >> C;

        adj[A].push_back({B, C});

        adj[B].push_back({A, C});

    }

    ll ans = INF, x, y, cur = 0;

    cin >> x >> y;

    for (i = 0; i < 2; i++, swap(x, y), cur = 0) {

        dijkstra(1), cur += dst[x];

        if (dst[x] == INF or dst[y] == INF or dst[n] == INF) continue;

        dijkstra(x), cur += dst[y];

        dijkstra(y), cur += dst[n];

        ans = min(cur, ans);

    }

    if (ans == INF) {

        cout << "-1";

        return 0;

    }

    cout << ans;

    return 0;

}

---