結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2022-12-19 01:03:02 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 5,000 ms |
コード長 | 1,449 bytes |
コンパイル時間 | 3,483 ms |
コンパイル使用メモリ | 143,716 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-18 00:09:29 |
合計ジャッジ時間 | 5,275 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <iostream> #include <vector> #include <cmath> #include <map> #include <set> #include <iomanip> #include <queue> using namespace std; template<typename T> using pq = priority_queue<T, vector<T>, greater<T>>; int main(){ long long N, C, V, cost, mi=1e18; long long from, alt, d; cin >> N >> C >> V; pq<tuple<long long, long long, long long>> que; vector<vector<tuple<long long, long long, long long>>> E(N); vector<vector<long long>> dist(N, vector<long long>(C+1, 1e18)); vector<vector<bool>> visit(N, vector<bool>(C+1)); vector<long long> S(V), T(V), Y(V), M(V); for (int i=0; i<V; i++) cin >> S[i]; for (int i=0; i<V; i++) cin >> T[i]; for (int i=0; i<V; i++) cin >> Y[i]; for (int i=0; i<V; i++) cin >> M[i]; for (int i=0; i < V; i++){ E[S[i]-1].push_back({T[i]-1, M[i], Y[i]}); } dist[0][0] = 0; //dist, from, cost; que.push({0, 0, 0}); while(!que.empty()){ tie(d, from, cost) = que.top(); que.pop(); if (visit[from][cost]) continue; visit[from][cost] = 1; for (auto [t, m, y] : E[from]){ alt = d + m; if (cost+y <= C && alt < dist[t][cost+y]){ dist[t][cost+y] = alt; que.push({alt, t, cost+y}); } } } for (int i=0; i<=C; i++) mi = min(mi, dist[N-1][i]); cout << (mi ==1e18 ? -1 : mi) << endl; return 0; }