leetcode-go/poj/3159.candies/main.cc

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

const int N = 30000;
const int M = 150000;
const int INF = 0x3F3F3F3F;

int dist[N + 1];

struct E {
  int v;
  int c;
  E(int v, int c) : v(v), c(c) {}
  bool operator<(const E &that) const { return this->c > that.c; }
};

int main() {
  int n, m, a, b, c, t;
  scanf("%d %d", &n, &m);
  memset(dist, 0x3F, sizeof(dist));
  vector<vector<E>> adj(n + 1);
  for (int i = 0; i < m; i++) {
    scanf("%d %d %d", &a, &b, &c);
    adj[a].push_back(E(b, c));
  }
  priority_queue<E> pq;
  dist[1] = 0, t = 1;
  for (int i = 0; i < adj[1].size(); i++) pq.push(adj[1][i]);
  while (t < n) {
    E e = pq.top();
    pq.pop();
    if (dist[e.v] <= e.c) continue;
    dist[e.v] = e.c;
    vector<E>::iterator it;
    for (it = adj[e.v].begin(); it != adj[e.v].end(); ++it)
      if (dist[it->v] == INF) pq.push(E(it->v, e.c + it->c));
    t++;
  }
  printf("%d\n", dist[n]);
  return 0;
}