백준(BOJ) 1238 : 파티

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

1238번: 파티

단방향 그래프가 주어졌을 때 도착점까지 왔다가 돌아올 수 있는 최단 거리중 최댓값을 구하는 문제.

 

다익스트라 알고리즘을 이용하여 각 정점들에 대해 도착점 -> 정점들의 거리를 일단 구해준다.

그 후에 각 정점들에 대해 다익스트라 알고리즘을 사용하여 정점 -> 도착점까지의 거리를 구한 뒤

앞에서 구한 도착점 -> 정점 까지의 거리를 더해준 것들 중 최댓값을 구해주면 된다.

 

아래는 소스코드이다.

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define cont continue
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 987654321;
int T;
vector< vector<pair<int, int> > > adj(1001);
int dist[1001] = {};
int dist2[1001] = {};

void foo(int start) {
  priority_queue< pair<int, int> > pq;
  pq.push(mp(start, 0));
  dist[start] = 0;
  while(!pq.empty()) {
    int here = pq.top().first;
    int DIST = -pq.top().second;
    pq.pop();
    if(DIST > dist[here]) continue;

    for(int i = 0 ; i < adj[here].size() ; i++) {
      int nxt = adj[here][i].first;
      int cost = adj[here][i].second;

      if(dist[nxt] > dist[here] + cost) {
        dist[nxt] = dist[here] + cost;
        pq.push(mp(nxt, -(dist[here] + cost)));
      }
    }
  } 
}

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

  int N, M, X;

  cin >> N >> M >> X;
  fill(dist, dist + 1001, INF);
  fill(dist2, dist2 + 1001, INF);

  for(int i = 0 ; i < M ; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    adj[a].pb(mp(b, c));
  }

  foo(X);

  for(int i = 1 ; i <= N ; i++) {
    dist2[i] = dist[i];
  }
  int ans = 0;

  for(int i = 1 ; i <= N ; i++) {
    fill(dist, dist + 1001, INF);
    foo(i);

    ans = max(dist2[i] + dist[X], ans);
  }
  cout << ans << endl;
}