Submission #3810224
Source Code Expand
#include <iostream> #include <vector> #include <queue> #include <utility> #include <math.h> #include <functional> #include <algorithm> using namespace std; typedef long long ll; ll income[10001]; ll n, m, t; struct edge{ int cost; int to; }; vector<edge> edges[10002]; vector<edge> edgesre[10002]; int main(){ ll monpermin[10001]; //��������_�C�N�X�g���@ cin >> n >> m >> t; for(ll i = 0;i < n;i ++) cin >> monpermin[i]; for(ll i = 0;i < m;i ++){ int s, t, d; cin >> s >> t >> d; edge pre = {d, t - 1}; edges[s - 1].push_back(pre); edge pre2 = {d, s - 1}; edgesre[t - 1].push_back(pre2); } ll ans[10002]; for(int i = 0;i < 10002;i ++) ans[i] = 2001001001; ans[0] = 0; ll ansre[10002]; for(int i = 0;i < 10002;i ++) ansre[i] = 2001001001; ansre[0] = 0; typedef pair<ll, ll> P; priority_queue<P, vector<P>, greater<P> > pq; priority_queue<P, vector<P>, greater<P> > pqre; pq.push(P(0,0)); pqre.push(P(0,0)); while(!pq.empty()){ P miria = pq.top(); pq.pop(); ll r = miria.second; if(ans[r] < miria.first){ continue; } for(int i = 0;i < edges[r].size();i ++){ int to=edges[r][i].to; int cost=edges[r][i].cost; if(ans[to] > ans[r] + cost ){ //�����Ă�Ƃ����m��{���ʂ�̂������� pq.push(P(ans[r] + cost, to)); //���̏������ ans[to] = ans[r] + cost; //�X�V } } }while(!pqre.empty()){ P miria = pqre.top(); pqre.pop(); ll r = miria.second; if(ansre[r] < miria.first){ continue; } for(int i = 0;i < edgesre[r].size();i ++){ int to=edgesre[r][i].to; int cost=edgesre[r][i].cost; if(ansre[to] > ansre[r] + cost){ //�����Ă�Ƃ����m��{���ʂ�̂������� pqre.push(P(ansre[r] + cost, to)); //���̏������ ansre[to] = ansre[r] + cost; //�X�V } } } /*for(int i = 0;i < n;i ++){ if(ans[i] < 2001001000) cout << ans[i] << endl; else cout << "INF" << endl; }*/ //�����܂Ń_�C�N�X�g���@ ll mx=0; for(int i = 0;i < n;i ++){ if(ans[i] < 2001001000){ income[i] = (t - (ans[i] + ansre[i])) * monpermin[i]; mx=max(income[i],mx); } else income[i] = 0; } cout << mx << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - トレジャーハント |
User | hana |
Language | C++14 (GCC 5.4.1) |
Score | 50 |
Code Size | 2391 Byte |
Status | RE |
Exec Time | 111 ms |
Memory | 4224 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 50 | 0 / 50 | ||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
Subtask1 | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 50_small_01.txt, 50_small_02.txt, 50_small_03.txt, 50_small_04.txt, 50_small_05.txt, 50_small_06.txt, 50_small_07.txt, 50_small_08.txt, 50_small_09.txt, 50_small_10.txt, 60_hand_01.txt, 60_hand_02.txt, 60_hand_03.txt, 60_hand_04.txt, 70_max_01.txt, 70_max_02.txt, 70_max_03.txt |
All | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 10_rand_06.txt, 10_rand_07.txt, 10_rand_08.txt, 10_rand_09.txt, 10_rand_10.txt, 10_rand_12.txt, 10_rand_13.txt, 30_max_01.txt, 30_max_02.txt, 30_max_03.txt, 30_max_04.txt, 30_max_05.txt, 30_max_06.txt, 40_corner_01.txt, 40_corner_02.txt, 40_corner_03.txt, 40_corner_04.txt, 50_small_01.txt, 50_small_02.txt, 50_small_03.txt, 50_small_04.txt, 50_small_05.txt, 50_small_06.txt, 50_small_07.txt, 50_small_08.txt, 50_small_09.txt, 50_small_10.txt, 60_hand_01.txt, 60_hand_02.txt, 60_hand_03.txt, 60_hand_04.txt, 70_max_01.txt, 70_max_02.txt, 70_max_03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 2 ms | 896 KB |
00_example_02.txt | AC | 2 ms | 896 KB |
00_example_03.txt | AC | 2 ms | 896 KB |
10_rand_01.txt | RE | 103 ms | 896 KB |
10_rand_02.txt | RE | 105 ms | 896 KB |
10_rand_03.txt | RE | 104 ms | 896 KB |
10_rand_04.txt | AC | 4 ms | 1024 KB |
10_rand_05.txt | RE | 105 ms | 896 KB |
10_rand_06.txt | RE | 107 ms | 896 KB |
10_rand_07.txt | RE | 111 ms | 896 KB |
10_rand_08.txt | RE | 105 ms | 896 KB |
10_rand_09.txt | RE | 107 ms | 896 KB |
10_rand_10.txt | RE | 104 ms | 1024 KB |
10_rand_12.txt | RE | 105 ms | 896 KB |
10_rand_13.txt | RE | 106 ms | 768 KB |
30_max_01.txt | RE | 104 ms | 896 KB |
30_max_02.txt | RE | 106 ms | 896 KB |
30_max_03.txt | AC | 88 ms | 4224 KB |
30_max_04.txt | RE | 107 ms | 896 KB |
30_max_05.txt | RE | 107 ms | 896 KB |
30_max_06.txt | RE | 107 ms | 896 KB |
40_corner_01.txt | RE | 105 ms | 896 KB |
40_corner_02.txt | RE | 105 ms | 896 KB |
40_corner_03.txt | RE | 106 ms | 896 KB |
40_corner_04.txt | RE | 106 ms | 896 KB |
50_small_01.txt | AC | 3 ms | 896 KB |
50_small_02.txt | AC | 2 ms | 896 KB |
50_small_03.txt | AC | 2 ms | 896 KB |
50_small_04.txt | AC | 2 ms | 896 KB |
50_small_05.txt | AC | 4 ms | 896 KB |
50_small_06.txt | AC | 3 ms | 896 KB |
50_small_07.txt | AC | 2 ms | 896 KB |
50_small_08.txt | AC | 2 ms | 896 KB |
50_small_09.txt | AC | 2 ms | 896 KB |
50_small_10.txt | AC | 2 ms | 896 KB |
60_hand_01.txt | AC | 2 ms | 896 KB |
60_hand_02.txt | AC | 2 ms | 896 KB |
60_hand_03.txt | AC | 2 ms | 896 KB |
60_hand_04.txt | AC | 2 ms | 896 KB |
70_max_01.txt | AC | 28 ms | 1792 KB |
70_max_02.txt | AC | 28 ms | 1792 KB |
70_max_03.txt | AC | 28 ms | 1792 KB |