結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2019-11-22 14:18:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 5,000 ms |
コード長 | 1,693 bytes |
コンパイル時間 | 2,576 ms |
コンパイル使用メモリ | 171,528 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:43:18 |
合計ジャッジ時間 | 2,927 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { // そのまま入力 int N, C, V; // N:街,C:金,V:辺 cin >> N >> C >> V; vector<int> S(V); //始点 vector<int> T(V); //終点 vector<int> Y(V); //金 vector<int> 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]; // dpで解く // 大きい値を用意 const int INF = 1e9; // dp[街][残金] = 最小時間 vector<vector<int>> dp(51,vector<int>(301,INF)); // 1番目の街を初期化 dp[1][C] = 0; // 1番目の街からN番目まで順に計算 for(int i = 0; i <= N; i++) { // 残金の値ごとに更新 for(int j = C; j >= 0; j--) { // 一度でも訪れていたらOK if(dp[i][j] != INF) { // すべての辺を探索 for(int k = 0; k < V; k++) { // 始点が一致している && 残金が条件以内 である辺 if(i == S[k] && j-Y[k] >= 0) { //dp[終点][計算後の残金] //= min(始点までの最小時間+始点から終点まで時間,そのまま) dp[T[k]][j-Y[k]] = min(dp[i][j]+M[k],dp[T[k]][j-Y[k]]); } } } } } // 解を出力 int ans = INF; for(int i = 0; i < 301; i++) ans = min(ans, dp[N][i]); if(ans == INF) cout << -1 << endl; else cout << ans << endl; return 0; }