結果

問題 No.1812 Uribo Road
ユーザー Nikita SkybytskyiNikita Skybytskyi
提出日時 2022-01-14 22:55:43
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
AC  
実行時間 118 ms / 5,000 ms
コード長 2,532 bytes
コンパイル時間 6,521 ms
コンパイル使用メモリ 140,912 KB
実行使用メモリ 5,372 KB
最終ジャッジ日時 2023-08-12 21:36:42
合計ジャッジ時間 8,856 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 12 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 3 ms
4,376 KB
testcase_09 AC 4 ms
4,376 KB
testcase_10 AC 3 ms
4,380 KB
testcase_11 AC 3 ms
4,376 KB
testcase_12 AC 62 ms
4,876 KB
testcase_13 AC 40 ms
4,544 KB
testcase_14 AC 36 ms
4,520 KB
testcase_15 AC 31 ms
4,380 KB
testcase_16 AC 30 ms
4,380 KB
testcase_17 AC 87 ms
4,696 KB
testcase_18 AC 42 ms
4,600 KB
testcase_19 AC 118 ms
5,372 KB
testcase_20 AC 116 ms
5,304 KB
testcase_21 AC 95 ms
5,340 KB
testcase_22 AC 85 ms
5,296 KB
testcase_23 AC 8 ms
4,380 KB
testcase_24 AC 2 ms
4,380 KB
testcase_25 AC 12 ms
4,380 KB
testcase_26 AC 2 ms
4,380 KB
testcase_27 AC 23 ms
4,380 KB
testcase_28 AC 22 ms
4,392 KB
testcase_29 AC 2 ms
4,376 KB
testcase_30 AC 4 ms
4,380 KB
testcase_31 AC 69 ms
4,784 KB
testcase_32 AC 4 ms
4,376 KB
testcase_33 AC 29 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
 * Author: nskybytskyi
 * Time:   2022-01-13 15:08:45
 */

#include <bits/stdc++.h>
using namespace std;

const int64_t inf = numeric_limits<int64_t>::max();

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int n, m, k;
  cin >> n >> m >> k;

  vector<int> r(k);
  for (auto& ri : r) {
    cin >> ri;
    --ri;
  }

  vector<tuple<int, int, int>> abc(m);
  for (auto& [a, b, c] : abc) {
    cin >> a >> b >> c;
    --a, --b;
  }

  vector<vector<pair<int, int>>> g(n);
  for (auto [a, b, c] : abc) {
    g[a].emplace_back(b, c);
    g[b].emplace_back(a, c);
  }

  set<int> special_set;
  special_set.insert(0);
  special_set.insert(n - 1);
  for (auto ri : r) {
    auto [a, b, _] = abc[ri];
    special_set.insert(a);
    special_set.insert(b);
  }

  vector<int> special(special_set.begin(), special_set.end());
  const int len = special.size();

  map<int, int> index;
  for (int i = 0; i < len; ++i) {
    index[special[i]] = i;
  }

  auto dijkstra = [&] (int s) -> vector<int64_t> {
    vector<int64_t> dist(n, inf);
    dist[s] = 0;
    priority_queue<pair<int64_t, int>,
                   vector<pair<int64_t, int>>,
                   greater<>> pq;

    pq.emplace(0, s);
    while (!pq.empty()) {
      auto [dv, v] = pq.top();
      pq.pop();
      if (dv == dist[v]) {
        for (auto [u, w] : g[v]) {
          if (dist[u] > dist[v] + w) {
            dist[u] = dist[v] + w;
            pq.emplace(dist[u], u);
          }
        }
      }
    }

    vector<int64_t> ans;
    for (auto f : special) {
      ans.push_back(dist[f]);
    }
    return ans;
  };


  vector<vector<int64_t>> dist;
  for (auto s : special) {
    dist.push_back(dijkstra(s));
  }

  vector<vector<int64_t>> dp(1 << k, vector<int64_t>(len, inf));
  dp[0][0] = 0;
  for (int mask = 0; mask < (1 << k); ++mask) {
    for (int curr = 0; curr < len; ++curr) {
      if (dp[mask][curr] < inf) {
        for (int next = 0; next < len; ++next) {
          dp[mask][next] = min(dp[mask][next], dp[mask][curr] + dist[curr][next]);
        }
      }
    }
    for (int curr = 0; curr < len; ++curr) {
      for (int i = 0; i < k; ++i) {
        auto [_a, _b, c] = abc[r[i]];
        auto a = index[_a], b = index[_b];
        if (dp[mask][a] < inf) {
          dp[mask | (1 << i)][b] = min(dp[mask | (1 << i)][b], dp[mask][a] + c);
        }
        if (dp[mask][b] < inf) {
          dp[mask | (1 << i)][a] = min(dp[mask | (1 << i)][a], dp[mask][b] + c);
        }
      }
    }
  }

  cout << dp[(1 << k) - 1].back() << "\n";

  return 0;
}
0