Submission #00105
ソースコード
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 | #include<bits/stdc++.h> using namespace std; struct Edge { int to, cost, hm, tw; Edge(){} Edge( int to, int cost, int hm, int tw) : to(to), cost(cost), hm(hm), tw(tw) {} bool operator < ( const Edge &a) const { return cost > a.cost; } }; int n, m; int k, z; int homo[102] = {}; vector<Edge> edge[102]; int main() { int a, b, d; cin>> n >> m >> k >> z; for ( int i = 1; i < n - 1; i++) cin>> homo[i]; for ( int i = 0; i < m; i++) { cin>> a >> b >> d; edge[a].push_back( Edge(b, d, 0, 0) ); edge[b].push_back( Edge(a, d, 0, 0) ); } int mx = -1; bool done[101][20001] = {}; priority_queue<Edge> que; que.push( Edge(0, 0, 0, z) ); while (!que.empty()) { Edge q = que.top(); que.pop(); if (done[q.to][q.hm]) continue ; done[q.to][q.hm] = true ; if (q.cost >= k) continue ; if (q.to == n - 1) { mx = max(mx, q.hm); } for ( int i = 0; i < edge[q.to].size(); i++) { que.push( Edge(edge[q.to][i].to, q.cost + edge[q.to][i].cost, q.hm + homo[edge[q.to][i].to], q.tw) ); if (q.tw > 0) que.push( Edge(edge[q.to][i].to, q.cost + edge[q.to][i].cost, q.hm + homo[edge[q.to][i].to] * 2, q.tw - 1) ); } } if (mx == -1) cout<< "Dead Homono" <<endl; else cout<< mx <<endl; return 0; } |
ステータス
項目 | データ |
---|---|
問題 | 0005 - れんさん退治 |
ユーザー名 | サウンド |
投稿日時 | 2017-08-08 10:53:47 |
言語 | C++11 |
状態 | Accepted |
得点 | 80 |
ソースコード長 | 1361 Byte |
最大実行時間 | 22 ms |
最大メモリ使用量 | 2452 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 80 / 80 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
input1.txt | AC | 22 ms | 2400 KB |
1
|
input2.txt | AC | 12 ms | 2452 KB |
1
|
input3.txt | AC | 17 ms | 2372 KB |
1
|