baekjoon 1238:파티

baekjoon 1238 파티

1238번 파티

접근

돌아가는 접근은 x에서 다익스트라 돌리고, 들어가는 접근은 x제외한 vertex에서
다익스트라 돌리고 x.d추가하면 됨.

코드

#include <iostream>
#include <vector>
#include <array>
#include <queue>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n, m, x; cin >> n >> m >> x;
  array<vector<pair<int, int>>, 1000> adj;
  for(int i = 0; i < m; i++){
    int a, b, t; cin >> a >> b >> t;
    adj[a-1].push_back({b-1, t});
  }
  array<int, 1000> dist;
  array<bool, 1000> visited;
  fill(dist.begin(), dist.begin() + n, 1e9);
  fill(visited.begin(), visited.begin() + n, false);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; //min queue이용한다
  dist[x-1] = 0;
  q.push({0, x-1});
  while(!q.empty()){
    pair<int, int> curr = q.top();
    q.pop();
    if(visited[curr.second]) continue; //여기서 전 업데이트 기록(v.d가 min이 아니였던 기록) 무시해줄거다
    visited[curr.second] = true;
    for(auto& i: adj[curr.second]){
      if(dist[i.first] > dist[curr.second]+i.second){
        dist[i.first] = dist[curr.second]+i.second;
        q.push({dist[i.first], i.first}); //어짜피 min queue에서 min을 뽑으니까 전에 있던걸 찾아서 pop할 이유는 없다
      }
    }
  }
  for(int i = 0; i < n; i++){
    if(i == x-1) continue;
    array<int, 1000> dist2;
    array<bool, 1000> visited2;
    fill(dist2.begin(), dist2.begin() + n, 1e9);
    fill(visited2.begin(), visited2.begin() + n, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q2;
    dist2[i] = 0;
    q2.push({0, i});
    while(!q2.empty()){
      pair<int, int> curr = q2.top();
      q2.pop();
      if(visited2[curr.second]) continue;
      visited2[curr.second] = true;
      for(auto& i: adj[curr.second]){
        if(dist2[i.first] > dist2[curr.second]+i.second){
          dist2[i.first] = dist2[curr.second]+i.second;
          q2.push({dist2[i.first], i.first});
        }
      }
    }
    dist[i] += dist2[x-1];
  }
  int max = 0;
  for(int i = 0; i < n; i++){
    if(i == x-1) continue;
    if(dist[i] > max) max = dist[i];
  }
  cout << max;

  return 0;

}

배운 점

다익스트라 알고리즘 구현연습한거다.
다익스트라가 ElogV의 시간복잡도를 가지고 있다.
생각보다 매우 빠른 알고리즘이다.