제출 #1287426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287426		kerem	날다람쥐 (JOI14_ho_t4)	C++20	100 / 100	188 ms	26076 KiB

2014_ho_t4

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pb push_back
#define emb emplace_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define N 100000
#define inf (int)1e14
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;

int n,m,X,h[N+5],dist[N+5];
vector<ii> g[N+5];
void solve(){
	cin >> n >> m >> X;
	for(int i=1;i<=n;i++)
		cin >> h[i];
	for(int i=0;i<m;i++){
		int x,y,t;
		cin >> x >> y >> t;
		g[x].emb(y,t);
		g[y].emb(x,t);
	}
	int ans=-1;
	priority_queue<iii,vector<iii>,greater<iii>> pq;
	memset(dist,-1,sizeof(dist));
	pq.push({0,X,1});
	while(!pq.empty()){
		int d,x,i;
		tie(d,x,i)=pq.top();
		pq.pop();
		if(i==n){
			ans=d+h[n]-x;
			break;
		}
		if(dist[i]!=-1)
			continue;
		dist[i]=d;
		for(auto [j,t]:g[i]){
			if(dist[j]==-1 && t<=h[i]){
				if(x<t) pq.push({d+t+t-x,0,j});
				else if(x-t>h[j]) pq.push({d+x-h[j],h[j],j});
				else pq.push({d+t,x-t,j});
			}
		}
	}
	cout << ans << endl;
}
int32_t main(){
	//~ freopen("hopscotch.in","r",stdin);
	//~ freopen("hopscotch.out","w",stdout);
	
	cout << fixed << setprecision(0);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

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