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
AC × 3
AC × 20
AC × 22
RE × 20
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