Submission #17031
ソースコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | #include <iostream> #include <stdio.h> #include <sstream> #include <string> #include <vector> #include <map> #include <queue> #include <algorithm> #include <set> #include <math.h> #include <utility> #include <stack> #include <string.h> #include <complex> using namespace std; const int INF = 1<<29; const double EPS = 1e-8; typedef vector< int > vec; typedef pair< int , int > P; struct edge{ int to,cost;}; struct node{ int d,c,n; bool operator<( const node& right ) const { return d == right.d ? c < right.c : d > right.d; } }; int main(){ int c, n, m, s, goal; scanf ( "%d%d%d%d%d" ,&c,&n,&m,&s,&goal); s--;goal--; vector<vector<edge> > g(n); for ( int i=0;i<m;i++){ int a, b, f; scanf ( "%d%d%d" ,&a,&b,&f); a--;b--; g[a].push_back((edge){b,f}); g[b].push_back((edge){a,f}); } vector<vec> d(c+1,vec(n,INF)); d[c][s] = 0; priority_queue<node> que; que.push((node){0,c,s}); int ans = INF; while (que.size()){ node p = que.top(); que.pop(); //printf("n=%d d=%d c=%d\n",p.n,p.d,p.c); if (d[p.c][p.n] < p.d) continue ; if (p.n == goal){ ans = p.d; break ; } for ( int i=0;i<g[p.n].size();i++){ int to = g[p.n][i].to; if (p.c > 0){ int dist_to_use_c = p.d + g[p.n][i].cost/2; if (d[p.c-1][to] > dist_to_use_c){ d[p.c-1][to] = dist_to_use_c; //printf("pushed d=%d c=%d n=%d\n",dist_to_use_c,p.c-1,to); que.push((node){dist_to_use_c,p.c-1,to}); } } int dist_to = p.d + g[p.n][i].cost; if (d[p.c][to] > dist_to){ d[p.c][to] = dist_to; //printf("pushed d=%d c=%d n=%d\n",dist_to,p.c,to); que.push((node){dist_to,p.c,to}); } } } cout << ans << endl; return 0; } |
ステータス
項目 | データ |
---|---|
問題 | 0717 - 高速バス |
ユーザー名 | ei1501 |
投稿日時 | 2017-05-10 19:01:38 |
言語 | C++11 |
状態 | Accepted |
得点 | 5 |
ソースコード長 | 2231 Byte |
最大実行時間 | 21 ms |
最大メモリ使用量 | 676 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 5 / 5 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
input01.txt | AC | 12 ms | 480 KB |
1
|
input02.txt | AC | 10 ms | 432 KB |
1
|
input03.txt | AC | 12 ms | 520 KB |
1
|
input04.txt | AC | 10 ms | 596 KB |
1
|
input05.txt | AC | 12 ms | 668 KB |
1
|
input06.txt | AC | 13 ms | 600 KB |
1
|
input07.txt | AC | 21 ms | 676 KB |
1
|
input08.txt | AC | 14 ms | 612 KB |
1
|
input09.txt | AC | 12 ms | 664 KB |
1
|
input10.txt | AC | 12 ms | 608 KB |
1
|