AOJ2249 Road Construction

問題

Road Construction | Aizu Online Judge

頂点、辺の連結グラフが与えられる。各辺には距離と建設コストが与えられる。0番目が首都であり、各ノードから首都までの距離を与えられたグラフと同じにするものとして、一から連結グラフを生成するための最小コストを求めよ。

• 
• 

解法

与えられたグラフ上で首都からの単一始点最短路に使う辺のみ用いれば、元のグラフから首都と各点との距離を変えない状態で連結グラフを構築できる。最短路に使われる辺のうち、コストが最小の辺を選び、その和を取れば良い。ダイクストラのヒープの比較要素として、距離総和の次に使用した辺のコストを持てば、最短路かつ、その中で最小の辺を選ぶことが出来る。

int main() {

  for(int N, M; cin >> N >> M && (N|M);) {
    vector<vector<tuple<int, int, int>>> G(N);
    rep(_, M) {
      int u, v, d, c; cin >> u >> v >> d >> c;
      u--, v--;
      G[u].emplace_back(v, d, c);
      G[v].emplace_back(u, d, c);
    }

    PQ_G<tuple<int, int, int>> pq;
    pq.emplace(0, 0, 0);

    vector<int> dist(N, inf);

    ll ans = 0;
    while(!pq.empty()) {
      int d, c, p; tie(d, c, p) = pq.top(); pq.pop();
      if(dist[p] <= d) continue;
      dist[p] = d;
      ans += c;
      for(auto const& e: G[p]) {
        int _v, _d, _c; tie(_v, _d, _c) = e;
        if(dist[_v] <= d + _d) continue;
        pq.emplace(d + _d, _c, _v);
      }
    }
    cout << ans << endl;
  }

  return 0;
}