Top
問1.（前ページと同じ問題）
$n$ 個の頂点と $m$ 本のコストつき無向辺が与えられます。
$0$ 番の頂点から $n-1$ 番の頂点まで最小コストで行きたいとき、そのコストを求めてください。ルートが無ければそれを指摘してください。
・$2 \le n \le 5{,}000$
・$1 \le m \le n(n-1)/2$
・$1 \le$ コスト $\le 10^{4}$

SPFA でやってみる。
最悪計算量はベルマンフォードと同じ $O(nm)$ だが、
コストが正のランダムな密グラフだと、速度は
[速] ダイクストラ(前頁コード2. 3.) → SPFA → ダイクストラ(前頁コード1.) [遅]
という結果だった。SPFA は負辺があっても適用できるのが強み。

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct edge { int to, cost; };

int main(void) {
  constexpr int inf = 987654321;
  int n, m; scanf("%d%d", &n, &m);
  vector<vector<edge>> G(n, vector<edge>());
  for(int i=0; i<m; ++i) {
    int a, b, c; scanf("%d%d%d", &a, &b, &c);
    G[a].push_back(edge{b, c});
    G[b].push_back(edge{a, c});
  }
  vector<int> cost(n, inf);
  cost[0] = 0;
  vector<bool> inque(n, false);
  inque[0] = true;
  queue<int> que;
  que.push(0);
  while(!que.empty()) {
    int v = que.front(); que.pop();
    inque[v] = false;
    for(edge e : G[v]) {
      if(cost[e.to] > cost[v] + e.cost) {
        cost[e.to] = cost[v] + e.cost;
        if(!inque[e.to]) {
          inque[e.to] = true;
          que.push(e.to);
        }
      }
    }
  }
  int res = cost[n-1];
  if(res == inf) { res = -1; }
  printf("%d\n", res);
  return 0;
}

(ΦωΦ)＜つづく