結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2021-02-27 01:08:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 27 ms / 5,000 ms |
コード長 | 1,337 bytes |
コンパイル時間 | 1,847 ms |
コンパイル使用メモリ | 199,984 KB |
最終ジャッジ日時 | 2025-01-19 07:36:37 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int INF = 1e9; int S[1500]; int T[1500]; int Y[1500]; int M[1500]; int dist[51][301]; int main(void) { cin.tie(0); ios::sync_with_stdio(false); int N,C,V; cin >> N; cin >> C; cin >> 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=1;i<=N;i++) { for(int j=0;j<=C;j++) { dist[i][j] = 1e9; } } dist[1][0] = 0; priority_queue <pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pque; pque.push(make_pair(dist[1][0],make_pair(1,0))); while(!pque.empty()) { int now = pque.top().second.first; int cost = pque.top().second.second; if(dist[now][cost] < pque.top().first) { pque.pop(); continue; } pque.pop(); for(int i=0;i<V;i++) { if(now==S[i]) { if(cost + Y[i] <= C) { if(dist[T[i]][cost+Y[i]] > dist[now][cost] + M[i]) { dist[T[i]][cost+Y[i]] = dist[now][cost] + M[i]; pque.push(make_pair(dist[T[i]][cost+Y[i]],make_pair(T[i],cost+Y[i]))); } } } } } int res = 1e9; for(int i=0;i<=C;i++) { res = min(res,dist[N][i]); } if(res==1e9) { res = -1; } cout << res << '\n'; return 0; }