Submission #151420

#	Time	Username	Problem	Language	Result	Execution time	Memory
151420		TadijaSebez	날다람쥐 (JOI14_ho_t4)	C++11	100 / 100	283 ms	17820 KiB

2014_ho_t4

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=100050;
const ll inf=9e18;
int h[N],hi[N],n,m,X;
ll dist[N][2];
vector<pair<int,int>> E[N];
void Dijkstra()
{
	hi[1]=X;
	for(int i=2;i<=n;i++) dist[i][0]=dist[i][1]=inf;
	dist[1][0]=0;dist[1][1]=X;
	priority_queue<pair<ll,int>> pq;
	pq.push({0,1});
	pq.push({-X,-1});
	while(pq.size())
	{
		int u=pq.top().second;
		ll d=-pq.top().first;
		pq.pop();
		int t=u<0?1:0;
		u=abs(u);
		if(dist[u][t]!=d) continue;
		int H;
		if(t==1) H=0;
		else H=hi[u];
		for(auto e:E[u])
		{
			int v=e.first;
			int w=e.second;
			if(H<=w)
			{
				int go=w+w-H;
				if(dist[v][1]>dist[u][t]+go)
				{
					dist[v][1]=dist[u][t]+go;
					pq.push({-dist[v][1],-v});
				}
			}
			else
			{
				int go=max(w,H-h[v]);
				if(dist[v][0]>dist[u][t]+go)
				{
					dist[v][0]=dist[u][t]+go;
					hi[v]=H-go;
					pq.push({-dist[v][0],v});
				}
			}
		}
	}
}
int main()
{
	scanf("%i %i %i",&n,&m,&X);
	for(int i=1;i<=n;i++) scanf("%i",&h[i]);
	for(int i=1,u,v,w;i<=m;i++)
	{
		scanf("%i %i %i",&u,&v,&w);
		if(h[u]>=w) E[u].pb({v,w});
		if(h[v]>=w) E[v].pb({u,w});
	}
	Dijkstra();
	ll ans=min(dist[n][1]+h[n],dist[n][0]+h[n]-hi[n]);
	printf("%lld\n",ans>=inf?-1:ans);
	return 0;
}

Compilation message (stderr)

2014_ho_t4.cpp: In function 'int main()':
2014_ho_t4.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&m,&X);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
2014_ho_t4.cpp:58:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i",&h[i]);
                        ~~~~~^~~~~~~~~~~~
2014_ho_t4.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i %i",&u,&v,&w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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