[백준 1753] 최단경로

www.acmicpc.net/problem/1753

1753번: 최단경로

다익스트라 알고리즘을 힙을 사용해서 구현하는 문제이다.

eazymean.tistory.com/290

[알고리즘] Dijkstra 다익스트라 알고리즘

다익스트라 알고리즘 쉬운줄 알았는데^^;; 생각보다 어려웠다.

 

배열을 사용해도 되지만 시간 복잡도가 n^2이 되므로 힙을 사용하자.

#include <stdio.h>
#include <vector>
#include <queue>
#define INF 5000000

using namespace std;
int v, e, k;

struct s
{
  int v, w;
};

struct cmp
{
  bool operator()(const s &t1, const s &t2)
  {
    if (t1.w == t2.w)
    {
      return t1.v > t2.v;
    }
    return t1.w > t2.w;
  }
};
vector<s> arr[20001];
int dis[20001];

priority_queue<s, vector<s>, cmp> pq;
int main(void)
{
  scanf("%d%d%d", &v, &e, &k);

  for (int i = 0; i < e; i++)
  {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    arr[u].push_back({v, w});
  }

  for (int i = 1; i <= v; i++)
  {
    dis[i] = INF;
  }

  dis[k] = 0;
  pq.push({k, 0});

  while (!pq.empty())
  {
    s cur = pq.top();
    pq.pop();

    int cv = cur.v;
    int cw = cur.w;
    if (dis[cv] < cw) // 이미 최솟값
      continue;

    for (int i = 0; i < arr[cv].size(); i++)
    {
      int nw = cw + arr[cv][i].w;
      int nv = arr[cv][i].v;

      if (nw < dis[nv])
      {
        dis[nv] = nw;

        pq.push({nv, nw});
      }
    }
  }

  for (int i = 1; i <= v; i++)
  {
    if (dis[i] == INF)
    {
      printf("INF\n");
    }
    else
    {
      printf("%d\n", dis[i]);
    }
  }

  return 0;
}