結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2015-06-17 20:31:39 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 243 ms / 5,000 ms |
コード長 | 2,790 bytes |
コンパイル時間 | 1,343 ms |
コンパイル使用メモリ | 150,252 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:15:45 |
合計ジャッジ時間 | 3,446 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#ifndef _GLIBCXX_NO_ASSERT #include <cassert> #endif #include <cctype> #include <cerrno> #include <cfloat> #include <ciso646> #include <climits> #include <clocale> #include <cmath> #include <csetjmp> #include <csignal> #include <cstdarg> #include <cstddef> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> //#ifdef __GXX_EXPERIMENTAL_CXX0X__ #include <ccomplex> #include <cfenv> #include <cinttypes> #include <cstdbool> #include <cstdint> #include <ctgmath> #include <cwchar> #include <cwctype> //#endif #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector> #include <array> //#include <atomic> #include <chrono> //#include <condition_variable> #include <forward_list> //#include <future> #include <initializer_list> //#include <mutex> #include <random> #include <ratio> #include <regex> #include <system_error> //#include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> using namespace std; typedef pair<int , int> P; vector<vector<int>>data; int main () { int N , C , V; cin >> N; cin >> C; cin >> V; vector<int>S ( V ) , T ( V ) , Y ( V ) , M ( V ); for( size_t i = 0; i < V; i++ ) { cin >> S[i]; S[i]--; } for( size_t i = 0; i < V; i++ ) { cin >> T[i]; T[i]--; } for( size_t i = 0; i < V; i++ ) { cin >> Y[i]; } for( size_t i = 0; i < V; i++ ) { cin >> M[i]; } data.resize ( N ); for( size_t i = 0; i < N; i++ ) { data[i].resize ( C + 1 ); for( size_t j = 0; j < C + 1; j++ ) { data[i][j] = INT_MAX / 3; } } data[0][0] = 0; priority_queue<P , vector<P> , greater<P>>que; que.push ( P{ 0 , 0 } ); while( que.size () ) { P now = que.top (); que.pop (); int now_p = now.second; for( size_t i = 0; i < V; i++ ) { if( S[i] == now_p ) { for( size_t j = 0; j + Y[i] < C + 1; j++ ) { if( data[T[i]][j + Y[i]] > data[now_p][j] + M[i] ) { data[T[i]][j + Y[i]] = data[now_p][j] + M[i]; que.push ( P{ data[T[i]][j + Y[i]] , T[i] } ); } } } } } int ans = INT_MAX / 6; for( size_t i = 0; i < C + 1; i++ ) { ans = min ( ans , data[N - 1][i] ); } if( ans == INT_MAX / 6 ) { cout << -1 << endl; } else { cout << ans << endl; } return 0; }