[백준 1238] 파티 (C++) - soo:bak

문제 링크

1238번 - 파티

설명

그래프에서의 최단 경로 탐색 알고리즘에 관한 문제입니다.

문제의 조건을 보면 가중치가 음수인 간선이 없으며, 그래프의 크기가 작지 않습니다.

따라서, 가중치가 있는 그래프의 최단 경로 탐색 알고리즘 중 Dijkstra 알고리즘을 사용하여 풀이합니다.

주어진 조건들이 복잡하지 않아서, Dijkstra 알고리즘에 대한 기본적인 이해를 확인하는 문제라고 생각합니다.

그래프에서의 최단 경로 탐색 알고리즘들에 대한 자세한 설명은 여기 에서 확인하실 수 있습니다.

---

Code

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

typedef pair<int, int> pii;

vector<vector<pii>> adj;
int cntStu, cntRoad, nodeX;

vector<int> dijkstra(int nodeS, int cntNode) {
  vector<int> dist(cntNode, INF);
  dist[nodeS] = 0;

  priority_queue<pii> pq;
  pq.push({0, nodeS});
  while (!pq.empty()) {
    int cost = -pq.top().first, nodeCur = pq.top().second;
    pq.pop();

    if (dist[nodeCur] < cost) continue ;

    for (size_t i = 0; i < adj[nodeCur].size(); i++) {
      int u = adj[nodeCur][i].first, ud = cost + adj[nodeCur][i].second;
      if (dist[u] > ud) {
        dist[u] = ud;
        pq.push({-ud, u});
      }
    }
  }
  return dist;
}

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

  cin >> cntStu >> cntRoad >> nodeX;

  adj.resize(cntStu + 1);
  for (int i = 0; i < cntRoad; i++) {
    int roadS, roadE, w; cin >> roadS >> roadE >> w;
    adj[roadS].push_back({roadE, w});
  }

  int ans = -1;
  for (int numStu = 1; numStu <= cntStu; numStu++) {
    vector<int> distStuToX = dijkstra(numStu, cntStu + 1);
    vector<int> distXtoStu = dijkstra(nodeX, cntStu + 1);
    if (distStuToX[nodeX] + distXtoStu[numStu] >= INF || distStuToX[nodeX] + distXtoStu[numStu] < 0)
      continue ;
    ans = max(ans, distStuToX[nodeX] + distXtoStu[numStu]);
  }

  cout << ans << "\n";

  return 0;
}