solution.cpp

#include <iostream>
#include <cstring>
#include <queue>
#include <climits>

using namespace std;

const int N = 1e3 + 10, M = 2e6 + 10;

int h[N], e[M], ne[M], w[M], idx;
int dist[N];
int n, m, k;
bool st[N]; // 标记数组

// 初始化
void init() {
  memset(h, -1, sizeof h);
  idx = 0;
}

// 添加一条边
void add(int a, int b, int c) {
  e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

// Dijkstra 算法求最短路径
void dijkstra(int s) {
  memset(dist, 0x3f, sizeof dist);
  dist[s] = 0;

  priority_queue<pair<int, int>> q; // 小根堆
  q.push({0, s});

  while (q.size()) {
    auto t = q.top();
    q.pop();
    int ver = t.second, distance = t.first;
    if (st[ver]) continue;
    st[ver] = true;

    // 更新所有 ver 相邻的点
    for (int i = h[ver]; ~i; i = ne[i]) {
      int j = e[i];
      if (dist[j] > distance + w[i]) {
        dist[j] = distance + w[i];
        q.push({dist[j], j});
      }
    }
  }
}

int main() {
  // 读入
  scanf("%d%d%d", &n, &m, &k);
  init();

  // 建图
  while (m--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    add(a, b, c);
  }

  // 求最短路径
  dijkstra(1);

  // 输出最短路径
  printf("%d\n", dist[n]);

  return 0;
}