Submission #140380

#	Time	Username	Problem	Language	Result	Execution time	Memory
140380		nhc7502	날다람쥐 (JOI14_ho_t4)	C++14	100 / 100	373 ms	28020 KiB

2014_ho_t4

///EVERYONE BELIEVE IN GODTAEGYU
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e15;
long long n, m, i, j, k;
long long x, h[100141];
long long dist[100141];
vector<pair<int,int>>graph[100141];
priority_queue<pair<long long, int>>pq;

int main(){
	iostream::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	for(cin>>n>>m>>x; i++<n;)
	{
		cin>>h[i];
		dist[i] = -INF;
	}
	for(;m--;)
	{
		cin>>i>>j>>k;
		if(h[i] >= k)
			graph[i].push_back({j, k});
		if(h[j] >= k)
			graph[j].push_back({i, k});
	}
	pq.push({x, 1});
	while(!pq.empty())
	{
		tie(m, i) = pq.top();
		pq.pop();
		if(dist[i] != -INF)continue;
		dist[i] = m;
		for(auto next : graph[i])
		{	//i = 현재 나무, m = 현재 높이, j = 다음 나무, k = 다음 나무 거리
			tie(j, k) = next;
			pq.push({min(m - k, h[j]), j});
		}
	}
	if(dist[n] == -INF) cout<<-1;
	else cout<<x + h[n] - dist[n] * 2;
	/*
	if 양수 -> 유지할 수 있는 최소 높이
	따라서 (x-dist[n]) + (h[n]-dist[n])
	if 음수 -> x는 다 쓴 이후 나무사이 가는데 최소거리(올라가는거 고려 X)
	따라서 (h[n]-dist[n]) -> 올라가는데 필요한 비용
	x-dist[n] -> 날아가는데 필요한 비용
	*/
	return 0;
}

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