Beakjoon 1238 파티

28 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/1238

나의 풀이

이 문제도 다익스트라 알고리즘을 이용하여 문제를 해결할 수 있다. X에서 다른 정점으로의 거리 뿐 아니라 다른 정점에서 X까지의 거리도 구해야하기 때문에 모든 정점에대해 다익스트라 알고리즘을 적용하여 모든 정점사이의 최소 길이를 구해야한다.
A에서 B까지의 최단거리를 dist[A][B]라고 할 때 그 거리중 X를 왕복하는 거리의 최댓값은 dist[X][i] + dist[i][X]의 최댓값이다.

풀이 코드 : 1238 파티

#include <iostream>
#include <vector>
#include <queue>

#define INF 2000000000

using namespace std;

struct info{
    int next;
    int w;
};

vector<vector<info>> graph; 
vector<vector<int>> dist;

void dijkstra(int start, int N){
    vector<int> visit;
    visit.resize(N+1);
    dist[start].resize(N+1);
    for(int i=1;i<=N;i++){
        dist[start][i] = INF;
    }

    priority_queue<pair<int, int>> pq;
    dist[start][start] = 0;
    pq.push(make_pair(0, start));
    while(!pq.empty()){
        int curr = pq.top().second;
        pq.pop();
        if(visit[curr] == 1) continue;
        visit[curr] = 1;
        for(int i=0;i<graph[curr].size();i++){
            int next = graph[curr][i].next;
            int w = graph[curr][i].w;

            if(visit[next] != 1 && dist[start][next] > w + dist[start][curr]){
                dist[start][next] = w + dist[start][curr];
                pq.push(make_pair(-dist[start][next], next));
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, X;
    cin>>N>>M>>X;

    graph.resize(N+1);
    dist.resize(N+1);
    
    int start;
    info temp;
    for(int i=0;i<M;i++){
        cin>>start>>temp.next>>temp.w;
        graph[start].push_back(temp);
    }
    for(int i=1;i<=N;i++){
        dijkstra(i, N);
    }

    int answer = dist[X][1] + dist[1][X];
    for(int i=2;i<=N;i++){
        if(dist[X][i] + dist[i][X] > answer){
            answer = dist[X][i] + dist[i][X];
        }
    }

    cout<<answer;
}

채점결과