yutasの競技プログラミング勉強帖

競技プログラミングの問題についての解説記事を主に書いています。

G - Bicycles / Codeforces Round 918 (Div. 4)

CF1915 Codeforces C++ Div.4 Codeforces Round 918 Diff 1800 グラフ 最短経路 競技プログラミング

問題

n 個の町があり、これらの町の間には m 本の道路があり、道路 i は町 {u}_{i} と町 {v}_{i} を結び、その長さは {w}_{i} である。

また、どの町にも必ず自転車が1台売られており、町 i での自転車の速度指標は {s}_{i} である。 ここで速度指標とは、その自転車を使用することにより掛かる時間の指標であり、道路 i を自転車 j で通行するには {w}_{i} \cdot {s}_{j} の時間が掛かる。

自転車を何台でも購入することができるとき、自転車を使って町 1 から町 n へと辿り着くための最小時間を求めよ。 ただし、自転車を使わずに道路の通行はできないものとする。

入力

まず最初の1行目に、テストケースの個数を表す整数 t が与えられる。

その後、 t 個のテストケースのそれぞれに対して、以下のように入力が与えられる。

  • 最初の1行目には、整数 n, m が与えられる。
  • 次の m 行のうち i 行目には、道路 i の情報を表す整数 {u}_{i}, \, {v}_{i}, \, {w}_{i} が順に与えられる。
  • 次の1行には、整数 {s}_{1}, \, {s}_{2}, \, \cdots , \, {s}_{n} が順に与えられる。

条件

  • 実行時間制限: 4s
  • メモリ制限: 256MB
  • 1 \leq t \leq 100
  • 2 \leq n \leq 1000
  • n - 1 \leq m \leq 1000
  • 1 \leq {u}_{i}, {v}_{i} \leq n
    • {u}_{i} \ne {v}_{i}
    • i \ne j のとき、 ({u}_{i}, \, {v}_{i}) \ne ({u}_{j}, \, {v}_{j})
    • すべての町同士は、1本以上の道路を経由して移動することができる。
  • 1 \leq {w}_{i} \leq {10}^{5}
  • 1 \leq {s}_{i} \leq 1000

出力

t 行にわたり、各テストケースについての答えを出力すること。

解法

まず、具体的な状況を考えるために、問題の例の1つ目として与えられている以下のような状況について考えます。

このときの、各町同士の最短距離はそれぞれ以下の図のようになります。

まず最初の時点では、町 1 にいることから、自転車 1 のみを用いて他の町に行くことを考えます。 このとき、先程の距離の表と {s}_{1} = 5 であることから、現時点で考えられる各町へと辿り着く最小時間は以下の図のようになります。

得られた表より、町 2 へ到着する時間が最小となるため、町 1 から町 2 への最小時間は 10 ということが確定します。 これは、町 1 から他の町を経由して町 2 に辿り着こうとしても、他の町を経由した地点で町 2 へ直接行くときよりも時間がかかってしまうためです。

従って、次に町 2 から、自転車 2 を用いて他の町に行くことを考えます。 町 1 から町 2 への最小時間が 10 であり、 {s}_{2} = 2 であることから、この時点で考えられる各町へと辿り着く最小時間は以下に示されます。

この表から、次に最小となるのは町 3 へと到着する時間となるため、町 1 から町 3 への最小時間は 12 ということが確定します。

従って、同様にして町 3 から、自転車 3 を用いて他の町に行くと、以下のように図を更新することができます。

ここで、自転車 4, \, 5 を使用しても、今回の例の場合では最小時間を更に更新することはできなかったということが言えます。

以上の手順を踏むことにより、町 1 から町 5 へと到着するのにかかる最小時間は 19 ということが言えます。

従って、これを一般化した方法によって、町 1 から町 n へと到着するのに必要な最小時間が求められると考えられます。 具体的には、

  1. 1 \leq i, \, j \leq n であるすべての整数組 (i, \, j) について、町 i から町 j の最短距離を求める
  2. 町 1 から自転車 1 のみを使用したときの、各町への最小到達時間を求める
  3. その中から町 1 以外で値が最小となる町（これを v とします）の値を確定する
  4. 町 v から自転車 v のみを使用したときの、各町への最小到達時間を求める
  5. 手順3, 4を時間が確定していない町がなくなるまで繰り返す

という手順によって、町 1 からすべての町へと到着するのに必要な最小時間を求めることができます。

この方法では、手順1の段階で O({n}^{2}) の計算量がかかり、手順2から手順5までの部分でも O({n}^{2}) の計算量がかかります。 この問題の条件から、 n \leq 1000 であるので、この方法で実行時間制限に十分間に合うと考えられます。

従って、以上の手順で導出されたものから、町 1 から町 n へと到着するのに必要な最小時間を出力すれば、この問題を解くことができたと言えます。

ソースコード

まず与えられたグラフ上で、点 start からの距離を計算する calc_dist() 関数を以下のように実装しました。

vector<Pli> graph[1005]; // graph[i] には、頂点 i からの道が (距離, 行き先) の pair<ll, int> の形で保存されている
ll dist[1005][1005]; // dist[i][j] は点 i から点 j までの距離を表す
bool visited[1005]; // visited[i] は点 i を訪問したかどうかを表す

void calc_dist(int start) { // 点 start からの距離を計算する
  fill(visited + 1, visited + n + 1, false); // visited の初期化
  priority_queue<Pli, vector<Pli>, greater<Pli>> que; // (距離, 行き先) の組を距離の小さい順に管理する priority_queue
  que.push({0, start}); // (0, start) をキューに入れる

  // キューの中身がなくなるまで以下を繰り返す
  while (!que.empty()) {
    Pli now = que.top();
    que.pop();

    // もし既にキューの先頭にある頂点を訪問済であれば、再度探索する必要はない
    if (visited[now.second]) {
      continue;
    }

    visited[now.second] = true; // 現在の頂点を訪問済とする
    dist[start][now.second] = now.first; // start から現在の頂点までの最短距離を確定させる

    for (Pli next : graph[now.second]) {
      // 未訪問の頂点に関して、キューに値を挿入する
      if (!visited[next.second]) {
        // 「現在の頂点までの最短距離 + 次の頂点への道の長さ」が次の頂点への最短距離の候補となる
        que.push({now.first + next.first, next.second});
      }
    }
  }
  return;
}

この calc_dist() 関数が実装されている状態で、問題の答えを返す solve() 関数を以下のように実装しました。

int n, m;
vector<Pli> graph[1005]; // graph[i] には、頂点 i からの道が (距離, 行き先) の pair<ll, int> の形で保存される
ll s[1005];
ll ans[1005]; // ans[i] は点 1 から点 i までの最小時間を表す
ll dist[1005][1005]; // dist[i][j] は点 i から点 j までの距離を表す
bool visited[1005]; // visited[i] は点 i を訪問したかどうかを表す

ll solve() {
  // 値の入力
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    ll w;
    cin >> u >> v >> w;
    graph[u].push_back({w, v});
    graph[v].push_back({w, u});
  }
  for (int i = 1; i <= n; i++) {
    cin >> s[i];
  }

  // calc_dist() を用いて、すべての2点間の距離を計算する
  for (int i = 1; i <= n; i++) {
    calc_dist(i);
  }

  // visited の初期化
  fill(visited + 1, visited + n + 1, false);
  priority_queue<Pli, vector<Pli>, greater<Pli>> que; // (経過時間, 行き先) の組を経過時間の小さい順に管理する priority_queue
  que.push({0, 1}); // 点1 には時間0で到着可能なので、キューに入れる

  // キューの中身がなくなるまで、以下を繰り返す
  while (!que.empty()) {
    Pli now = que.top();
    que.pop();

    // もし既にキューの先頭にある頂点を訪問済であれば、再度探索する必要はない
    if (visited[now.second]) {
      continue;
    }
    visited[now.second] = true; // 現在の頂点を訪問済とする
    ans[now.second] = now.first; // 現在の頂点への最短時間を確定させる

    // 1 から n までのすべての頂点について、 dist を用いて最短時間の候補をキューに入れる
    for (int j = 1; j <= n; j++) {
      // もし点 j が訪問済であれば、キューに入れる必要はない
      if (visited[j]) {
        continue;
      }
      // 「現在の頂点までの最短時間 + s[i] * dist[i][j] 」が次の頂点への最短距離の候補となる
      que.push({now.first + s[now.second] * dist[now.second][j], j});
    }
  }

  return ans[n]; // 点 n への最短時間を返す
}

感想

メタ的な読みにはなってしまうのですが、 n \leq 1000 の条件から O({n}^{2}) 程度の計算量で間に合うようなもので考えようという方針になりました。

全然本題とは関係ないですが、今回作成した画像をgif画像化したら、こんな感じになりました。 ダイクストラ法の考え方の参考など、何かの参考になったら嬉しいです。