日々精進

aikoと旅行とプログラミング

【AOJ ALDS1_12】C: Graph Ⅱ - Single Source Shortest Path Ⅱ

問題

最短経路 | アルゴリズムとデータ構造 | Aizu Online Judge

方針

  • 隣接行列を用いたダイクストラ法はグラフG=(V, E)において {O(|V|^2)}となる.
  • 今回はノード数が {1 \leq n \leq 10000}であるので, 隣接リストを使った実装を行う.
  • 隣接リストでグラフを表現し, 二分ヒープ(priority_queue)を用いることで飛躍的に高速化することができる.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define ALL(v) v.begin(), v.end()
#define mp make_pair
#define INF 1e9
#define MAX 10000

using namespace std;

typedef pair<int, int> pii;

int n;
// pair.first : 距離
// pair.second : 頂点
vector<pii> node[MAX];
bool root[MAX];
int d[MAX];

void dijkstra(){
  priority_queue<pii> pq;  
  rep(i, MAX){
    d[i] = INF;
    root[i] = false;
  }
  
  d[0] = 0;
  pq.push(mp(0, 0));

  while(!pq.empty()){
    pii p = pq.top(); pq.pop();
    int u = p.second;
    
    root[u] = true;
    
    if(d[u] < p.first * -1) continue;
    
    rep(i, node[u].size()){
      int v = node[u][i].first;
      if(root[v]) continue;
      if(d[v] > d[u] + node[u][i].second){
    d[v] = d[u] + node[u][i].second;
    pq.push(mp(d[v] * -1, v));
      }
    }
  }
}

signed main(){
  cin >> n;
  int u, k, v, c;
  rep(i, n){
    cin >> u >> k;
    rep(j, k){
      cin >> v >> c;
      node[u].pb(mp(v, c));
    }
  }

  dijkstra();
    
  rep(i, n){
    cout << i << " " << (d[i] == INF?-1:d[i]) << endl;
  }
}