graph.dij

graph.dij.cc

vi dij(vvi&neigh, vvi&cost, int s) {
  const int n = neigh.size();
  vi d(n, inf); d[s] = 0;
  priority_queue<pair<int, int>> q; q.push({0, s});
  while (not q.empty()) {
    int u = q.top().second; q.pop();
    for (int v: neigh[u]) {
      int d2 = d[u] + cost[u][v];
      if (d2 < d[v]) {
        d[v] = d2;
        q.push({ -d2, v });
      }
    }
  }
  return d;
}

Example

入力形式

解答

int main() {
  int n, m; cin >> n >> m;
  vvi neigh(n);
  vvi cost(n, vi(n, 0));
  rep (i, m) {
    int a, b, c; cin >> a >> b >> c;
    --a; --b;
    neigh[a].push_back(b);
    cost[a][b] = cost[b][a] = c;
  }

  auto result = dij(neigh, cost, 0);
  cout << result << endl;

  return 0;
}