Submission #95324

#	Time	Username	Problem	Language	Result	Execution time	Memory
95324		Retro3014	날다람쥐 (JOI14_ho_t4)	C++17	100 / 100	313 ms	27584 KiB

2014_ho_t4

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <queue>

using namespace std;
#define MAX_N 100000
#define MAX_M 300000
#define INF 1000000000000000000LL
typedef long long ll;

int N, M;
struct S{
	int idx;
	ll data;
};
vector<S> gp[MAX_N+1];
ll H[MAX_N+1];
ll X;
struct S2{
	S2 (int idx, ll h, ll t) : idx(idx), h(h), t(t) {}
	int idx;
	ll h, t;
	bool operator <(const S2 &a)const{
		return t>a.t;
	}
};
priority_queue<S2> pq;

ll dist[MAX_N+1];
ll dist2[MAX_N+1];
ll ans = INF;


int main(){
	scanf("%d%d%lld", &N, &M, &X);
	for(int i=1; i<=N; i++){
		scanf("%lld", &H[i]);
	}
	for(int i=0; i<M; i++){
		int a, b;
		ll c;
		scanf("%d%d%lld", &a, &b, &c);
		gp[a].push_back({b, c}); gp[b].push_back({a, c});
	}
	for(int i=1; i<=N; i++)	dist[i] = dist2[i] = INF;
	pq.push({1, X, 0});
	if(X==0)	dist[1] = 0;
	else dist2[1] = 0;
	while(!pq.empty()){
		S2 now = pq.top(); pq.pop();
		if(now.idx==N){
			ans = min(ans, now.t+H[N]-now.h);
		}
		if(now.h==0){
			if(dist[now.idx]!=now.t)	continue;
			for(int i=0; i<gp[now.idx].size(); i++){
				if(gp[now.idx][i].data>H[now.idx])	continue;
				int nxt = gp[now.idx][i].idx;
				if(dist[nxt]>dist[now.idx]+gp[now.idx][i].data*2){
					dist[nxt] = dist[now.idx]+gp[now.idx][i].data*2;
					pq.push({nxt, (ll)0, dist[nxt]});
				}
			}
		}else{
			if(dist2[now.idx]!=now.t)	continue;
			for(int i=0; i<gp[now.idx].size(); i++){
				int nxt = gp[now.idx][i].idx;
				if(gp[now.idx][i].data<now.h){
					if(now.h-gp[now.idx][i].data>H[nxt]){
						if(dist2[nxt]>now.t+gp[now.idx][i].data+now.h-gp[now.idx][i].data-H[nxt]){
							dist2[nxt] = now.t+gp[now.idx][i].data+now.h-gp[now.idx][i].data-H[nxt];
							pq.push({nxt, H[nxt], dist2[nxt]});						
						}
					}
					else{
						if(dist2[nxt]>now.t+gp[now.idx][i].data){
							dist2[nxt] = now.t+gp[now.idx][i].data;
							pq.push({nxt, now.h-gp[now.idx][i].data, dist2[nxt]});						
						}
					}
				}else{
					if(gp[now.idx][i].data>H[now.idx])	continue;
					if(dist[nxt]>now.t+gp[now.idx][i].data*2-now.h){
						dist[nxt] = now.t+gp[now.idx][i].data*2-now.h;
						pq.push({nxt, 0, dist[nxt]});
					}
				}
			}
		}
	}
	if(ans==INF)	printf("-1");
	else printf("%lld", ans);
}

Compilation message (stderr)

2014_ho_t4.cpp: In function 'int main()':
2014_ho_t4.cpp:58:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0; i<gp[now.idx].size(); i++){
                 ~^~~~~~~~~~~~~~~~~~~
2014_ho_t4.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0; i<gp[now.idx].size(); i++){
                 ~^~~~~~~~~~~~~~~~~~~
2014_ho_t4.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld", &N, &M, &X);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
2014_ho_t4.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &H[i]);
   ~~~~~^~~~~~~~~~~~~~~
2014_ho_t4.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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