본문으로 바로가기

다익스트라 알고리즘을 사용하여 문제를 해결할 수 있다.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 3000000;

vector<vector<pair<int, int>>> edge;
vector<int> dist;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
int v, e, k;

void dijkstra(int);

int main() {
  scanf("%d %d %d", &v, &e, &k);

  edge.resize(v+1);
  dist.resize(v+1);

  int x, y, z;
  for (int i=0; i<e; i++) {
    scanf("%d %d %d", &x, &y, &z);
    edge[x].push_back({y, z});
  }

  dijkstra(k);

  for (int i=1; i<=v; i++) {
    dist[i] == INF ? printf("INF\n") : printf("%d\n", dist[i]);
  }
  return 0;
}

void dijkstra(int s) {
  fill(dist.begin(), dist.end(), INF);
  dist[s] = 0;// 시작점에서 시작점 까지는 비용이 0이다

  pq.push({0, s});// 정점 s에서 출발
  while (!pq.empty()) {
    int cNode = pq.top().second;// 현재 방문 중인 노드
    int cCost = pq.top().first;// 현재까지 비용
    pq.pop();

    // 보다 적은 비용을 미리 구해놓았다면 무시
    if (dist[cNode] < cCost) continue;

    for (auto e: edge[cNode]) {
      int nNode = e.first;
      int nCost = e.second;
      if (cCost + nCost < dist[nNode]) {
        dist[nNode] = cCost + nCost;
        pq.push({cCost + nCost, nNode});
      }// 새로 방문할 경로의 비용이 더 적다면 갱신
    }// 현재 방문 중인 정점과 연결된 간선 탐색
  }
}

'Programming > Baekjoon Online Judge' 카테고리의 다른 글

[BOJ] 1238: 파티  (0) 2018.06.14
[BOJ] 11404: 플로이드  (0) 2018.06.12
[BOJ] 1753: 최단 경로  (0) 2018.06.12
[BOJ] 14621: 나만 안되는 연애  (0) 2018.06.12
[BOJ] 1647: 도시 분할 계획  (0) 2018.06.12
[BOJ] 1197: 최소 스패닝 트리  (0) 2018.06.12

댓글을 달아 주세요