結果
問題 | No.3111 Toll Optimization |
ユーザー |
![]() |
提出日時 | 2025-04-19 06:05:18 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 268 ms / 5,000 ms |
コード長 | 1,569 bytes |
コンパイル時間 | 1,083 ms |
コンパイル使用メモリ | 139,552 KB |
実行使用メモリ | 15,828 KB |
最終ジャッジ日時 | 2025-04-19 06:05:31 |
合計ジャッジ時間 | 12,021 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 70 |
ソースコード
#include <iostream> #include <vector> #include <queue> using namespace std; #define MAX_V 100002 #define INF 1e17 typedef pair<int, int> pii; typedef tuple<long long, int, int> tiii; struct edge{ int to, d; }; int V,E,K; long long weight[MAX_V][4]; vector<edge> G[MAX_V]; void dijkstra(int s) { priority_queue<tiii, vector<tiii>, greater<tiii>> Q; Q.push({0, s, K}); weight[s][K] = 0; while (!Q.empty()) { auto [cost, v, coupons] = Q.top(); Q.pop(); if (weight[v][coupons] < cost) continue; for (int i = 0; i < (int)G[v].size(); i++) { edge &e = G[v][i]; if (coupons > 0 && weight[v][coupons] < weight[e.to][coupons-1]) { weight[e.to][coupons-1] = weight[v][coupons]; Q.push({weight[e.to][coupons-1], e.to, coupons-1}); } if ((long long)weight[v][coupons] + e.d < weight[e.to][coupons]) { weight[e.to][coupons] = weight[v][coupons] + e.d; Q.push({weight[e.to][coupons], e.to, coupons}); } } } } void init() { for (int i = 0; i < MAX_V; i++) { G[i].clear(); for (int j = 0; j < 4; j++) { weight[i][j] = INF; } } cin >> V >> E >> K; vector<int> toll(E); for (int i = 0; i < E; i++) { cin >> toll[i]; } for (int i = 0; i < E; i++) { int u, v; cin >> u >> v; u--; v--; G[u].push_back({v, toll[i]}); G[v].push_back({u, toll[i]}); } } int main() { init(); dijkstra(0); long long ans = INF; for (int i = 0; i < 4; i++) { ans = min(ans, weight[V-1][i]); } cout << (ans == INF ? -1 : ans) << endl; }