結果

問題 No.3111 Toll Optimization
ユーザー ZOI-dayo
提出日時 2025-04-11 19:09:59
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 247 ms / 5,000 ms
コード長 1,175 bytes
コンパイル時間 3,756 ms
コンパイル使用メモリ 292,264 KB
実行使用メモリ 19,708 KB
最終ジャッジ日時 2025-04-15 10:06:06
合計ジャッジ時間 13,493 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll INF = 1e15;

int main() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<ll> c(m);
  for (int i = 0; i < m; i++) {
    cin >> c[i];
  }
  vector g(n, vector<pair<ll, int>>());
  for(int i=0; i<m; i++) {
    int u, v;
    cin >> u >> v;
    u--; v--;
    g[u].push_back({c[i], v});
    g[v].push_back({c[i], u});
  }

  vector dist(n, vector<ll>(k+1, INF));
  dist[0] = {0, 0};
  priority_queue<pair<ll, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> pq;
  pq.push({0, {0, 0}});
  while (!pq.empty()) {
    auto [d, qv] = pq.top();
    auto [q, v] = qv;
    pq.pop();
    if (dist[v][q] < d) continue;
    for(auto [cost, nxt] : g[v]) {
      if(dist[nxt][q] > d + cost) {
        dist[nxt][q] = d + cost;
        pq.push({dist[nxt][q], {q, nxt}});
      }
      if(q < k && dist[nxt][q+1] > d) {
        dist[nxt][q+1] = d;
        pq.push({dist[nxt][q+1], {q+1, nxt}});
      }
    }
  }
  ll ans = INF;
  for(int i=0; i<=k; i++) {
    ans = min(ans, dist[n-1][i]);
  }
  if(ans == INF) {
    cout << -1 << endl;
  } else {
    cout << ans << endl;
  }

}
0