結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2014-12-06 14:39:51 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 2,160 bytes |
コンパイル時間 | 761 ms |
コンパイル使用メモリ | 80,576 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:07:31 |
合計ジャッジ時間 | 1,936 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <cstring> #include <ctime> #include <string> #include <vector> #include <stack> #include <queue> #include <map> #include <set> #include <algorithm> #include <cmath> #include <sstream> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; #define all(c) (c).begin(), (c).end() #define loop(i,a,b) for(ll i=a; i<ll(b); i++) #define rep(i,b) loop(i,0,b) #ifdef DEBUG #define dump(...) (cerr<<#__VA_ARGS__<<" = "<<(DUMP(),__VA_ARGS__).str()<<" ["<<__LINE__<<"]"<<endl) struct DUMP:ostringstream{template<class T>DUMP &operator,(const T&t){if(this->tellp())*this<<", ";*this<<t;return *this;}}; #else #define dump(...) #endif // グラフ用ヘッダ typedef int Time; typedef int Cost; struct Edge { int src, dst; Time time; Cost cost; Edge(int src = 0, int dst = 0, Time time = 0, Cost cost = 0) : src(src), dst(dst), time(time), cost(cost) { } }; bool operator < (const Edge &e, const Edge &f) { return e.time != f.time ? e.time > f.time : // !!INVERSE!! e.src != f.src ? e.src < f.src : e.dst < f.dst; } typedef vector<Edge> Edges; typedef vector<Edges> Graph; int V,E; int C; Graph g; int S[1500],T[1500],Y[1500],M[1500]; // 頂点,お金 -> 時間の最小値 int dp[60][400]; int main(){ while(cin>>V>>C>>E){ Edges es(E); for(auto arr : {S,T,Y,M}){ rep(i,E) cin >> arr[i]; } rep(i,E){ es[i] = Edge(S[i],T[i],M[i],Y[i]); } sort(all(es), [](const Edge& a, const Edge& b){ return a.src < b.src; }); rep(i,60)rep(j,400)dp[i][j] = 1<<29; dp[1][0] = 0; for(auto& e:es){ for(int i=0;i<=C-e.cost;i++){ dp[e.dst][i+e.cost] = min(dp[e.dst][i+e.cost], dp[e.src][i]+e.time); } } int ans = 1<<29; for(int i=0;i<=C;i++){ ans = min(ans, dp[V][i]); } if(ans==1<<29)ans=-1; cout << ans << endl; } }