Submission #3810208
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 | Bash (GNU bash v4.3.11) |
Score | 0 |
Code Size | 2391 Byte |
Status | RE |
Exec Time | 8 ms |
Memory | 644 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | RE | 8 ms | 644 KB |
00_example_02.txt | RE | 5 ms | 640 KB |
00_example_03.txt | RE | 5 ms | 588 KB |
10_rand_01.txt | RE | 5 ms | 644 KB |
10_rand_02.txt | RE | 5 ms | 608 KB |
10_rand_03.txt | RE | 5 ms | 644 KB |
10_rand_04.txt | RE | 5 ms | 608 KB |
10_rand_05.txt | RE | 5 ms | 612 KB |
10_rand_06.txt | RE | 5 ms | 604 KB |
10_rand_07.txt | RE | 5 ms | 644 KB |
10_rand_08.txt | RE | 5 ms | 644 KB |
10_rand_09.txt | RE | 5 ms | 644 KB |
10_rand_10.txt | RE | 5 ms | 588 KB |
10_rand_12.txt | RE | 5 ms | 608 KB |
10_rand_13.txt | RE | 5 ms | 584 KB |
30_max_01.txt | RE | 5 ms | 588 KB |
30_max_02.txt | RE | 5 ms | 604 KB |
30_max_03.txt | RE | 5 ms | 616 KB |
30_max_04.txt | RE | 5 ms | 644 KB |
30_max_05.txt | RE | 5 ms | 644 KB |
30_max_06.txt | RE | 5 ms | 644 KB |
40_corner_01.txt | RE | 5 ms | 588 KB |
40_corner_02.txt | RE | 5 ms | 608 KB |
40_corner_03.txt | RE | 5 ms | 588 KB |
40_corner_04.txt | RE | 5 ms | 640 KB |
50_small_01.txt | RE | 5 ms | 644 KB |
50_small_02.txt | RE | 5 ms | 640 KB |
50_small_03.txt | RE | 5 ms | 608 KB |
50_small_04.txt | RE | 5 ms | 608 KB |
50_small_05.txt | RE | 5 ms | 608 KB |
50_small_06.txt | RE | 5 ms | 608 KB |
50_small_07.txt | RE | 5 ms | 632 KB |
50_small_08.txt | RE | 5 ms | 608 KB |
50_small_09.txt | RE | 5 ms | 644 KB |
50_small_10.txt | RE | 5 ms | 572 KB |
60_hand_01.txt | RE | 5 ms | 640 KB |
60_hand_02.txt | RE | 5 ms | 640 KB |
60_hand_03.txt | RE | 5 ms | 644 KB |
60_hand_04.txt | RE | 5 ms | 584 KB |
70_max_01.txt | RE | 5 ms | 588 KB |
70_max_02.txt | RE | 5 ms | 644 KB |
70_max_03.txt | RE | 5 ms | 640 KB |