[1238] 파티

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

1238번: 파티

<문제>

처음에 주어지는 X에 대한 다익스트라의 결과값을 미리 base[]에 저장해두고

i=[1, n] 에 대해 dst[x]+base[i]의 최대값을 구하면된다.

역추적이 없으니 보다 구현이 간단하지만, 다익스트라의 시간복잡도에 대한 이해,

다익스트라가 구하는것의 의미를 잘 알아야 풀 수 있는 문제인것 같다. 

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MAX_N = 100000, INF = (ll)1e17;
 
ll n, m, s, e, dst[MAX_N + 1], path[MAX_N + 1];
typedef struct {
    ll idx, cost;
} state;
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]});
                path[nxt.idx] = cur.idx;
            }
        }
    }
    return;
}
void findPath(vector<ll>& ret) {
    ll cur = e;
    path[s] = -1;
    for (;; cur = path[cur]) {
        if (cur <= 0) break;
        ret.push_back(cur);
    }
    reverse(ret.begin(), ret.end());
    return;
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> e;
    ll i;
    for (i = 0; i < m; i++) {
        ll A, B, C;
        cin >> A >> B >> C;
        adj[A].push_back({B, C});
    }
    ll ans = 0;
    ll base[MAX_N + 1] = {0};
    dijkstra(e);
    memcpy(base, dst, sizeof(dst));
    for (i = 1; i <= n; i++) {
        s = i;
        dijkstra(i);
        ll score = base[i] + dst[e];
        ans = max(score, ans);
    }
    cout << ans;
    return 0;
}