結果

問題 No.3111 Toll Optimization
コンテスト
ユーザー shibh308
提出日時 2025-04-18 23:39:02
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 446 ms / 5,000 ms
コード長 1,188 bytes
コンパイル時間 3,889 ms
コンパイル使用メモリ 214,356 KB
実行使用メモリ 19,636 KB
最終ジャッジ日時 2025-04-18 23:39:32
合計ジャッジ時間 15,644 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include "atcoder/all"

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")

using namespace std;

using i64 = long long;


void solve(){
  int n, m, K;
  cin >> n >> m >> K;
  vector<i64> c(m);
  vector<vector<pair<int,i64>>> edges(n);
  for(int i = 0; i < m; ++i){
    cin >> c[i];
  }
  for(int i = 0; i < m; ++i){
    int a, b;
    cin >> a >> b;
    --a, --b;
    edges[a].emplace_back(b, c[i]);
    edges[b].emplace_back(a, c[i]);
  }
  vector<vector<i64>> dp(n, vector<i64>(K + 1, 1e18));
  priority_queue<tuple<i64, int, int>, vector<tuple<i64, int, int>>, greater<tuple<i64, int, int>>> pq;
  dp[0][0] = 0;
  pq.emplace(0, 0, 0);
  while(!pq.empty()){
    auto [d, v, k] = pq.top();
    pq.pop();
    if(dp[v][k] < d) continue;
    for(auto [u, w] : edges[v]){
      if(dp[u][k] > d + w){
        dp[u][k] = d + w;
        pq.emplace(dp[u][k], u, k);
      }
      if(k != K && dp[u][k + 1] > d){
        dp[u][k + 1] = d;
        pq.emplace(dp[u][k + 1], u, k + 1);
      }
    }
  }
  i64 ans = 1e18;
  for(int i = 0; i <= K; ++i){
    ans = min(ans, dp[n - 1][i]);
  }
  cout << (ans == 1e18 ? -1 : ans) << endl;
}

signed main(){
  solve();
}
0