파티 1238번 [백준]

www.acmicpc.net/problem/1238

이번 문제는 다익스트라 알고리즘을 이용하여 풀었습니다.

다익스트라 알고리즘은 우선순위 큐를 이용하여 풀었고, 소가 시작지점에서 도착지점 그리고 도착지점에서 시작지점까지 가는데에 걸리는 시간의 최댓값을 구해야 했기에, 처음 했던 생각은 단순히 모든 각각의 노드에서 출발하는 경우를 구해서 그중 최댓값을 구했었습니다.

 

하지만, 더 시간을 줄이기 위해, 기존의 일방향 그래프 이외에도 반대방향의 그래프도 만들어내어, x를 기준으로 원래의 가중치 그래프에서의 각각의 노드에 가는데에 걸리는 시간을 구했고, 또 x에서 반대 가중치 그래프에서 각각 노드에게 가는데 걸리는 시간을 구했습니다.

 

그 두개에서 나온 거리합의 최대값은 답을 의미하기에, 시간을 더 줄일 수 있었습니다.

 

#import<bits/stdc++.h>

using namespace std;
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second


const int INF = 987654321;

vector<pii> weight[1001];
vector<pii> weight2[1001];
int N,M,x;
vector<int> solve(int start,int m, vector<pii> *weight){
	priority_queue<pii,vector<pii>,greater<pii>> pq;
    vector<int> dist(m,INF);
    dist[start] = 0;
    pq.push({0,start});//0 is start to start's distance,1 is start node
    while(!pq.empty()){
        int cur = pq.top().ss;//출발지점에서부터 (pq에 저장된것중) 가장 큰 거리를 가진 노드
        int cur_distance =  pq.top().ff;//출발지점에서 그 노드까지의 거리.
        pq.pop();
        if(dist[cur]< cur_distance)continue;
        //만약 저장되어있는 거리보다 더 클시에는 최단거리가 아니므로 스킵
        for(int i =0;i<weight[cur].size();i++){
            int next = weight[cur][i].ss;
            int next_distance = (weight[cur][i].ff) + cur_distance;
            // 시작 노드에서 cur과 연결된 노드까지의 거리값 초기화
            if(next_distance < dist[next]){
            //새로 연결된 노드가 기존 저장값보다 작다고 되어있을시 거리값 수정
                pq.push({next_distance,next});
                dist[next] = next_distance;
            }
        }
    }
    return dist;
}
int main() {
    fast_io;
    cin>>N>>M>>x;
    for(int i =0;i<M;i++){
        int a,b,c;
        cin>>a>>b>>c;
        weight[a].pb({c,b});//first에 거리(pq가 기준으로 삼는 값)를 넣어야 더 빨라짐
        weight2[b].pb({c,a});
    }
    int result = -1;
    vector<int> temp = solve(x,N+1,weight);// start to x
    vector<int> temp2 = solve(x,N+1,weight2);// x to start
    for(int i =1;i<=N;i++)
        result = max(result,temp[i] + temp2[i]);
    cout<<result;
    return 0;
}