ABC079D

問題

D - Wall

からに書き換えるには魔力が必要であるとき、を全て1に変えるのに必要な魔力の最小量を求めよ。

ただし、の場合は変えなくて良い。

解法

制約上、ワーシャルフロイド法で解けそうだったが、ダイクストラ法の経験が乏しかったため、ダイクストラ法で解くことにした。

考え方としては、数字を頂点に、書き換えるという動作を辺に、それに必要な魔力を辺の重みにすることで、各頂点から1への最短経路長を求めれば良いことになる。

これをダイクストラ法で解くとすると、1への距離を1以外の各頂点においてはINF、頂点1においては0で初期化し、1への距離が小さい順に各頂点において他の頂点の1への距離を更新していく。

あとは、各壁において必要な魔力の最小量を求めれば良い。

計算量は、ダイクストラ法においてはダイクストラ法 - Wikipedia によるとらしい（良くわかっていない）

もしそうであれば、今回は完全グラフなので、であり、計算量がになるので、priority_queueを使わない方法()の方が良かったのだろう。

ただ、今回の制約では各壁を探索するの方が大きくなる場合がほとんど なので、気にする必要は無い。

コード

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define INF 1000

int main() {
  int h, w; cin >> h >> w;
  VVI c(10, VI(10));
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) cin >> c[i][j];
  }

  VI d(10, INF);
  d[1] = 0;
  auto comp = [&](int a, int b) { return d[a] > d[b]; };
  priority_queue<int, VI, decltype(comp)> que(comp);
  que.push(1);
  while (!que.empty()) {
    int v = que.top(); que.pop();
    for (int u = 0; u < 10; u++) {
      if (d[u] > d[v] + c[u][v]) {
        d[u] = d[v] + c[u][v];
        que.push(u);
      }
    }
  }

  int ans = 0;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      int a; cin >> a;
      if (a >= 0) ans += d[a];
    }
  }
  cout << ans << endl;
}

感想

計算量って難しい。