rt，只AC了#5

提交记录

代码：

// Dijkstra 堆优
#include <iostream>
#include <queue>

using namespace std;

const int kMaxN = 1e5 + 1;
const int kMaxM = 2e5 + 1;

struct E {
  int y, w, n;
} e[kMaxM];

struct V {
  int et, d = (1 << 31) - 1;
  bool v;
} a[kMaxN];

struct D {
  int p, v;
  bool operator<(const D &o) const {
    return v < o.v;
  }
};

int n, m, s;
priority_queue<D> p;

int main() {
  cin >> n >> m >> s;
  for (int i = 1, x; i <= m; ++i) {
    cin >> x >> e[i].y >> e[i].w;
    e[i].n = a[x].et, a[x].et = i;
  }
  a[s].d = 0, p.push({s, 0});
  while (!p.empty()) {
    D x = p.top();
    p.pop();
    if (a[x.p].v) {
      continue;
    }
    a[x.p].v = 1;
    for (int i = a[x.p].et; i; i = e[i].n) {
      int &d = a[e[i].y].d;
      if (d > x.v + e[i].w) {
        d = x.v + e[i].w;
        if (!a[e[i].y].v) {
          p.push({e[i].y, d});
        }
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    cout << a[i].d << " ";
  }
  return 0;
}