結果
問題 | No.1 道のショートカット |
ユーザー | A8pf |
提出日時 | 2018-10-02 10:25:43 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 5 ms / 5,000 ms |
コード長 | 1,501 bytes |
コンパイル時間 | 782 ms |
コンパイル使用メモリ | 84,752 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:37:49 |
合計ジャッジ時間 | 1,738 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 3 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 3 ms
5,376 KB |
testcase_11 | AC | 3 ms
5,376 KB |
testcase_12 | AC | 5 ms
5,376 KB |
testcase_13 | AC | 4 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 1 ms
5,376 KB |
testcase_18 | AC | 1 ms
5,376 KB |
testcase_19 | AC | 1 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 4 ms
5,376 KB |
testcase_24 | AC | 3 ms
5,376 KB |
testcase_25 | AC | 2 ms
5,376 KB |
testcase_26 | AC | 2 ms
5,376 KB |
testcase_27 | AC | 4 ms
5,376 KB |
testcase_28 | AC | 2 ms
5,376 KB |
testcase_29 | AC | 3 ms
5,376 KB |
testcase_30 | AC | 2 ms
5,376 KB |
testcase_31 | AC | 2 ms
5,376 KB |
testcase_32 | AC | 3 ms
5,376 KB |
testcase_33 | AC | 2 ms
5,376 KB |
testcase_34 | AC | 3 ms
5,376 KB |
testcase_35 | AC | 2 ms
5,376 KB |
testcase_36 | AC | 3 ms
5,376 KB |
testcase_37 | AC | 2 ms
5,376 KB |
testcase_38 | AC | 1 ms
5,376 KB |
testcase_39 | AC | 1 ms
5,376 KB |
testcase_40 | AC | 2 ms
5,376 KB |
testcase_41 | AC | 2 ms
5,376 KB |
testcase_42 | AC | 1 ms
5,376 KB |
testcase_43 | AC | 2 ms
5,376 KB |
ソースコード
#include <iostream> #include <algorithm> #include <string> #include <vector> #include <cmath> #include <functional> #include <queue> using namespace std; typedef long long ll; typedef tuple<int,int,int> T;//時間、所持金、座標 class Edge { public: int cost; int time; int from; int to; Edge(int n,int t,int c) { to=n; time=t; cost=c; } Edge(int f,int t,int tt,int c) { from=f; to=t; time=tt; cost=c; } }; vector<Edge> g[50]; int dp[50][300]; int ss[1500]; int tt[1500]; int yy[1500]; int mm[1500]; int main() { int n,c,m; cin>>n>>c>>m; for(int i=0;i<m;i++) { cin>>ss[i]; ss[i]--; } for(int i=0;i<m;i++) { cin>>tt[i]; tt[i]--; } for(int i=0;i<m;i++) cin>>yy[i]; for(int i=0;i<m;i++) cin>>mm[i]; for(int i=0;i<m;i++) { g[ss[i]].push_back(Edge(tt[i],mm[i],yy[i])); } //ここからダイクストラ fill(dp[0],dp[50],1e9-1); dp[0][c]=0; priority_queue<T,vector<T>,greater<T>> que; que.push(make_tuple(0,c,0)); while(!que.empty()) { T cp=que.top();que.pop(); int now=get<2>(cp); int zan=get<1>(cp); int lap=get<0>(cp); //cerr<<now<<endl; for(int i=0;i<g[now].size();i++) { Edge e=g[now][i]; if(zan-e.cost>=0) { if(lap+e.time<dp[e.to][zan-e.cost]) { dp[e.to][zan-e.cost]=lap+e.time; que.push(make_tuple(lap+e.time,zan-e.cost,e.to)); } } } } //ダイクストラ終了 sort(dp[n-1],dp[n-1]+300); if(dp[n-1][0]==1e9-1) cout<<-1<<endl; else cout<<dp[n-1][0]<<endl; return 0; }