結果
問題 |
No.3111 Toll Optimization
|
ユーザー |
|
提出日時 | 2025-04-18 20:07:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 469 ms / 5,000 ms |
コード長 | 1,596 bytes |
コンパイル時間 | 1,939 ms |
コンパイル使用メモリ | 210,764 KB |
実行使用メモリ | 27,424 KB |
最終ジャッジ日時 | 2025-04-18 20:08:09 |
合計ジャッジ時間 | 19,393 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 70 |
ソースコード
#include <bits/stdc++.h> using namespace std; //#include<atcoder/all> //using namespace atcoder; using ll = long long int; using ull = unsigned long long int; using ld = long double; constexpr ll MAX = 2000000000000000000; constexpr ld PI = 3.14159265358979; constexpr ll MOD = 0;//2024948111; ld dotorad(ld K){ return PI * K / 180.0; } ld radtodo(ld K){ return K * 180.0 / PI; } mt19937 mt; void randinit(){ srand((unsigned)time(NULL));mt = mt19937(rand()); } int main(){ ll N,M,K; cin >> N >> M >> K; vector<ll> CC(M); for(ll i = 0; i < M; i++){ cin >> CC[i]; } vector<vector<ll>> G(N),C(N); for(ll i = 0; i < M; i++){ ll a,b; cin >> a >> b; a--;b--; G[a].emplace_back(b); G[b].emplace_back(a); C[a].emplace_back(CC[i]); C[b].emplace_back(CC[i]); } vector<vector<ll>> memo(K + 1,vector<ll>(N,MAX)); priority_queue<tuple<ll,ll,ll>,vector<tuple<ll,ll,ll>>,greater<tuple<ll,ll,ll>>> que; que.emplace(0,0,0); while(!que.empty()){ auto [cost,rank,now] = que.top(); que.pop(); if(memo[rank][now] <= cost) continue; memo[rank][now] = cost; for(ll i = 0; i < G[now].size(); i++){ ll next = G[now][i],c = C[now][i]; if(rank + 1 <= K){ que.emplace(cost,rank + 1,next); } que.emplace(cost + c,rank,next); } } ll ans = MAX; for(ll i = 0; i <= K; i++){ ans = min(ans,memo[i][N - 1]); } if(ans == MAX) cout << -1 << endl; else cout << ans << endl; }