Submission #541096

#	Time	Username	Problem	Language	Result	Execution time	Memory
541096		pokmui9909	날다람쥐 (JOI14_ho_t4)	C++17	100 / 100	238 ms	32620 KiB

2014_ho_t4

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define x first
#define y second
ll N, M, X;
ll H[100005];
vector<pair<ll, ll>> G[100005];
const ll INF = 1e15;
ll mh[100005];

int main(){
	cin.tie(0) -> sync_with_stdio(false);

	cin >> N >> M >> X;
	for(int i = 1; i <= N; i++){
		cin >> H[i];
		mh[i] = INF;
	}
	for(int i = 1; i <= M; i++){
		ll u, v, c; cin >> u >> v >> c;
		if(H[u] >= c) G[u].push_back({v, c});
		if(H[v] >= c) G[v].push_back({u, c});
	}
	priority_queue<pair<ll, ll>> PQ;
	PQ.push({X, 1});
	while(!PQ.empty()){
		ll d = PQ.top().x, u = PQ.top().y; PQ.pop();
		if(mh[u] != INF) continue;
		mh[u] = d;
		for(auto i : G[u]){
			if(mh[i.x] != INF) continue;
			PQ.push({min(d - i.y, H[i.x]), i.x});
		}
	}
	cout << (mh[N] == INF ? -1 : X + H[N] - mh[N] * 2);
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 50 / 50