BOJ 1238 파티

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

github : https://github.com/junho0956/Algorithm/blob/master/1238/1238/%EC%86%8C%EC%8A%A4.cpp

 

정점의 크기가 최대 1000이기 때문에

dist[i]+dist[X] 를 정점 i에서 X로 + 정점 X에서 정점 i로 가는 이동거리라고 생각했을 때

시간복잡도가 nlogn * n => n^2logn 이여도 시간내로 해결가능합니다!

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 987654321
typedef pair<int, int> pii;
 
int N, M, X;
bool visit[1001];
vector<pii> v[1001];
priority_queue<pii, vector<pii>, greater<pii> > q;
 
vector<int> dijkstra(int start) {
    vector<int> dist(N+1,INF);
    for (int i = 1; i <= N; i++)visit[i] = false;
    dist[start] = 0;
 
    q.push({ 0,start });
    while (!q.empty()) {
        int cur = q.top().second;
        int len = q.top().first;
        q.pop();
 
        if (visit[cur]) continue;
        visit[cur] = true;
 
        for (int i = 0; i < v[cur].size(); i++) {
            int vertex = v[cur][i].first;
            int distance = v[cur][i].second;
            if (!visit[vertex] && len + distance < dist[vertex]) {
                dist[vertex] = len + distance;
                q.push({ dist[vertex], vertex });
            }
        }
    }
 
    return dist;
}
 
void solve() {
    cin >> N >> M >> X;
    for (int i = 0; i < M; i++) {
        int s, e, w;
        cin >> s >> e >> w;
        v[s].push_back({ e,w });
    }
    vector<int> dist = dijkstra(X);
 
    int ans = -1;
    for (int i = 1; i <= N; i++) {
        if (i == X) continue;
        vector<int> dist2 = dijkstra(i);
 
        if (dist2[X] >= INF) continue;
        ans = max(ans, dist[i] + dist2[X]);
    }
 
    cout << ans;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}