結果
問題 | No.3111 Toll Optimization |
ユーザー |
|
提出日時 | 2025-03-20 14:22:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 428 ms / 5,000 ms |
コード長 | 1,504 bytes |
コンパイル時間 | 2,363 ms |
コンパイル使用メモリ | 205,076 KB |
実行使用メモリ | 49,476 KB |
最終ジャッジ日時 | 2025-04-15 10:05:08 |
合計ジャッジ時間 | 16,192 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 70 |
ソースコード
#include <bits/stdc++.h> #define mp make_pair #define eb emplace_back using namespace std; using ll = long long; using wgraph = vector<vector<pair<ll, ll>>>; constexpr ll inf = 2e18; vector<ll> dijkstra(int start, vector<vector<pair<ll, ll>>>& g) { priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q; vector<ll> dist(g.size(), inf); dist[start] = 0; q.push(mp(0, start)); while (!q.empty()) { auto p = q.top(); q.pop(); ll now = p.second; if (dist[now] < p.first) continue; for (auto& nx : g[now]) { if (dist[nx.first] > dist[now] + nx.second) { dist[nx.first] = dist[now] + nx.second; q.push(mp(dist[nx.first], nx.first)); } } } return dist; } int n,m,u,v,k,c[200000]; int main() { cin >> n >> m >> k; wgraph g(n * (k + 1)); for(int i = 0; i < m; i++){ cin >> c[i]; } for(int i = 0; i < m; i++){ cin >> u >> v; u--,v--; for(int j = 0; j <= k; j++){ g[n * j + u].eb(mp(n * j + v,c[i])); g[n * j + v].eb(mp(n * j + u,c[i])); if(j != k){ g[n * j + u].eb(mp(n * (j + 1) + v,0)); g[n * j + v].eb(mp(n * (j + 1) + u,0)); } } } auto dist = dijkstra(0,g); ll ans = inf; for(int i = 0; i <= k; i++){ ans = min(ans,dist[n * i + n - 1]); } cout << (ans == inf ? -1 : ans) << endl; }