백준 1238번 파티

#include <iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
 
int n, m, x;
vector<pair<int,int> > path[10001];
int come[1001][1001];// come[i][j]는 i에서 j까지 가는 최단경로를 저장하는 배열
void Comeback(int start) {
    queue<int> q;
    q.push(start);
    while (!q.empty()) {
        int locate = q.front();
        q.pop();
        for (int i = 0; i < path[locate].size(); i++) {
            //가는 경로가 없는경우0 또는 이미 존재하는 경로보다 더 빠른 경로가 있는 경우
            if (come[start][path[locate][i].first]==0||come[start][path[locate][i].first] > come[start][locate] + path[locate][i].second) {
                come[start][path[locate][i].first] = come[start][locate] + path[locate][i].second;
                q.push(path[locate][i].first);
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> x;
    for (int i = 0; i < m; i++) {
        int a, b, v;
        cin >> a >> b >> v;
        path[a].push_back(make_pair(b, v));
    }
    for (int i = 1; i <= n; i++) {
        Comeback(i);  // come[i][j]를 i에서 j까지 최단경로 구해주는 함수.
    }
    int Max = 0;
    for (int i = 1; i <= n; i++) {
        if (i == x) continue;
        Max = max(Max, come[i][x] + come[x][i]); //(i에서 x까지 가는 최단경로+x에서 i까지 최단경로)
    }
    cout << Max;
    return 0;
 
}
 

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

다익스트라 문제입니다. 

푸는 방법은 가는최단경로+오는최단경로를 구현하는 것입니다. 기본적인 다익스트라에 응용을 해주어서 

쉽게 풀 수 있는 문제였습니다.