백준 알고리즘 1238번 : 파티

링크

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

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

예제 입력 및 출력

풀이법

학생들이 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력하라고 했으므로 i번 정점에서 x까지 가는 시간 + x에서 i까지 되돌아오는 시간의 합중 가장 큰값을 출력해주면 되는 문제였습니다.

풀이 코드(C++)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
#include<tuple>
#include<functional>
#include<utility>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define MAX 1001
#define INF 1e9
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;

vector <pair<int,int>> adj[MAX]; // 노드들의 정보들을 담는 벡터

int n,m,x;

int dijk(int start,int end){
  vector<int> dist(MAX,INF); //최단거리를 저장하는 배열, dist배열 초기화 해준다.
  priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
  pq.push({0, start});
  dist[start] = 0;

  while(!pq.empty()){
    int weight = pq.top().first;
    int cur = pq.top().second;
    pq.pop();

    if(dist[cur] < weight) continue;
    if(cur == end) return dist[cur];
    for(int i = 0; i < adj[cur].size(); i++){
      int nWeight = adj[cur][i].first;
      int next = adj[cur][i].second;
      if(dist[next] > nWeight + weight){
        dist[next] = nWeight + weight;
        pq.push({dist[next], next});
      }
    }
  }
  return INF;
}

void Input(){
  cin >> n >> m >> x;
  for(int i = 0; i < m; i++){
    int a,b,c; cin >> a >> b >> c;
    adj[a].pb({c, b}); // 단방향임
  }
}

void Solution(){
  int ans = 0;
  int first1 = dijk(1, x);
  int first2 = dijk(x, 1);
  ans = first1 + first2;
  for(int i = 1; i <= n; i++){
    int temp1 = dijk(i, x); // i -> x
    int temp2 = dijk(x, i); // x -> i
    int result = temp1 + temp2;
    ans = max(ans, result);
  }
  cout << ans;
  return;
}

int main(){
  fastio;
  Input();
  Solution();
  return 0;
}