Submission #95751

#TimeUsernameProblemLanguageResultExecution timeMemory
95751easrui날다람쥐 (JOI14_ho_t4)C++14
0 / 100
5 ms2808 KiB
#include <bits/stdc++.h> #define va first #define vb second using namespace std; typedef pair<int,int> pii; const int MN = 1e5+5; int N,M,X,H[MN],a,b,t,pos; long long len,dis,D[MN],h,ans; vector<pii> G[MN]; struct node{ int a; long long d; node(){}; node(int x, long long y){a = x, d = y;}; bool operator < (const node &A) const{ return A.d<d; } }; priority_queue<node> pq; int main() { freopen("input.txt","r",stdin); ios_base::sync_with_stdio(0),cin.tie(0); cin >> N >> M >> X; for(int i=1; i<=N; i++) cin >> H[i]; for(int i=0; i<M; i++){ cin >> a >> b >> t; if(H[a]>=t) G[a].push_back(pii(t,b)); if(H[b]>=t) G[b].push_back(pii(t,a)); } for(int i=1; i<=N; i++) D[i] = 1e16; D[1] = 0; pq.push(node(1,0)); while(!pq.empty()){ pos = pq.top().a; len = pq.top().d; pq.pop(); //cout << pos << ' ' << len << '\n'; if(len>D[pos]) continue; for(pii cur : G[pos]){ if(len<X){ h = X - len; if(h<cur.va) dis = len + cur.va + (cur.va-h); else if(h>H[cur.vb]+cur.va) dis = X - H[cur.vb]; else dis = len + cur.va; } else dis = len + 2*cur.va; if(dis<D[cur.vb]){ D[cur.vb] = dis; //cout << cur.vb << '\n'; pq.push(node(cur.vb,dis)); } } } ans = D[N]<H[1] ? 2*D[N]+H[N]-H[1] : D[N]+H[N]; cout << ans; }

Compilation message (stderr)

2014_ho_t4.cpp: In function 'int main()':
2014_ho_t4.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("input.txt","r",stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...