Submission #140305

#	Time	Username	Problem	Language	Result	Execution time	Memory
140305		nhc7502	날다람쥐 (JOI14_ho_t4)	C++14	25 / 100	2036 ms	15352 KiB

2014_ho_t4

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

void f(int tree, int godo, int thist)
{
	if(dist.find({tree, godo}) == dist.end())
	{
		dist[{tree, godo}] = thist;
		pq.push({thist, {tree, godo}});
	}
	else if(dist[{tree, godo}] > thist)
	{
		dist[{tree, godo}] = thist;
		pq.push({thist, {tree, godo}});
	}
}

int main(){
	iostream::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	for(cin>>n>>m>>x; i<n;)
	{
		cin>>h[++i];
	}
	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});
	}
	dist[{1, x}] = 0;
	pq.push({0,{1,x}});
	while(!pq.empty())
	{
		x = pq.top().first;
		tie(m, i) = pq.top().second;
		pq.pop();
		if(dist[{m, i}] != x)
			continue;
		for(auto next : graph[m])
		{	//m = 현재 나무, i = 현재 높이, j = 다음 나무, k = 다음 나무 거리
			tie(j, k) = next;
			if(i < k) f(j, 0, x + k - i + k);
			else if(i - k > h[j]) f(j, h[j], x + i - h[j]);
			else f(j, i - k, x + k);
		}
		if(m == n)
			f(n, h[n], x + h[n] - i);
	}
	if(dist.find({n, h[n]}) == dist.end())
		cout<<-1;
	else cout<<dist[{n,h[n]}];
	return 0;
}

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