結果

問題 No.1812 Uribo Road
コンテスト
ユーザー Nikita Skybytskyi
提出日時 2022-01-14 22:55:43
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 115 ms / 5,000 ms
コード長 2,532 bytes
コンパイル時間 4,619 ms
コンパイル使用メモリ 173,824 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-20 13:30:42
合計ジャッジ時間 6,510 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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