1511 Invitation Cards

概要

有向グラフが与えられて，エッジにはコストがついている．
N頂点あったら，1番の頂点からN人の人をすべての頂点に行き渡るように移動させて，
そこから１番に返ってくるような，すべての人についてのコストの和の最小値を答えるという問題．
頂点も辺も100万まで．

解法

解き方はダイクストラなのですが，頂点と辺が異常に多いので，何とかしないといけない．．
そこでPKU用の高速なグラフ構造について書きます．
PKUが最適化をしてくれないせいでまたひとつバッドノウハウを覚えてしまいました．
以下のコードは擬似コードなので，足りないところは補ってくだしあ
ちなみに，いつもグラフの問題は，こんな感じで構造を作っています．

struct Edge {
  int to, cost;
};
typedef vector<vector<Edge> > Graph;
Graph g(N);

二重vectorは遅いので，シビアなときとか，頂点数が多いときは，vectorを一段下げて使いまわします．

struct Edge {
  int to, cost;
};
const int MN = 1000;
vector<Edge> g[MN];

これでも駄目なときは，最大次数を見極めて，配列の配列みたいにしていました．

struct Edge {
  int to, cost;
};
const int MN = 1000;
Edge g[MN][100];
int idx[MN];

でもよく考えるともっとうまいやり方があって，全体の辺の数がわかっているのでエッジ配列に詰め込んで，オフセットを付けて見てあげればいいんです．

struct Edge {
  int src, dst, cost;
  bool operator < (const Edge& e) const {
    if(src != e.src) return src < e.src;
    return dst < e.dst;
  }
};
const int MN = 1000, MM = 1000;
int deg[MN], acc[MN + 1];
Edge es[MM];
int N, M;

REP(i, M) {
  int s, t, c;
  es[i] = Edge(s, t, c);
  deg[s]++;
}
sort(es, es + M);
acc[0] = 0;
REP(i, N) acc[i + 1] = acc[i] + deg[i];

REP(i, N) {
  int offset = acc[i];
  REP(j, deg[i]) {
    Edge* it = &es[offset + j];
    // ...
  }
}

こんな感じで，頂点から出るエッジの数と，エッジ配列内のどこからその頂点からのエッジが始まるかのオフセットを計算しておくと，vectorを使わずにメモリも最小限で済みます．
sortをしなきゃいけないけれど，それを差し引いても速いです．

こんな日記でいいんでしょうかｗ