Submission #3810375

---

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[100001];

ll n, m, t;
struct edge{
	int cost;
	int to;
};
vector<edge> edges[100002];
vector<edge> edgesre[100002];
ll ans[100002];
ll ansre[100002];
ll monpermin[100001];


int main(){
	
	
	//こっからダイクストラ法
	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);
	}
	
	for(int i = 0;i < 100002;i ++) ans[i] = 2001001001;
	ans[0] = 0;
	
	
	for(int i = 0;i < 100002;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 ++){
			if(ans[edges[r][i].to] > ans[r] + edges[r][i].cost){ //今見てるとこより確定＋道通るのが小さい
				pq.push(P(ans[r] + edges[r][i].cost, edges[r][i].to)); //その情報入れる
				ans[edges[r][i].to] = ans[r] + edges[r][i].cost;  //更新
			}
		}
	}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 ++){
			if(ansre[edgesre[r][i].to] > ansre[r] + edgesre[r][i].cost){ //今見てるとこより確定＋道通るのが小さい
				pqre.push(P(ansre[r] + edgesre[r][i].cost, edgesre[r][i].to)); //その情報入れる
				ansre[edgesre[r][i].to] = ansre[r] + edgesre[r][i].cost;  //更新
			}
		}
	}
	/*for(int i = 0;i < n;i ++){
		if(ans[i] < 2001001000) cout << ans[i] << endl;
		else cout << "INF" << endl;
	}*/
	 //ここまでダイクストラ法
	
	for(int i = 0;i < n;i ++){
		if(ans[i] < 2001001000 && ansre[i] < 2001001000) income[i] = (t - (ans[i] + ansre[i])) * monpermin[i];
		else income[i] = 0;
	}
	sort(income, income + n, greater<ll>());
	
	cout << income[0] << endl;
	return 0;
}

Submission Info

Judge Result