Submission #140344

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

2014_ho_t4

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

inline pair<int,int> lltop(long long x)
{
	return {x/MOD, x%MOD};
}

inline long long ptoll(pair<int,int> x)
{
	return x.first * MOD + x.second;
}

void f(int tree, int godo, int thist)
{
	if(dist.find(ptoll({tree, godo})) == dist.end())
	{
		dist[ptoll({tree, godo})] = thist;
		pq.push({thist, {tree, godo}});
	}
	else if(dist[ptoll({tree, godo})] > thist)
	{
		dist[ptoll({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[ptoll({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[ptoll({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(ptoll({n, h[n]})) == dist.end())
		cout<<-1;
	else cout<<dist[ptoll({n,h[n]})];
	return 0;
}

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