Submission #95324

#TimeUsernameProblemLanguageResultExecution timeMemory
95324Retro3014날다람쥐 (JOI14_ho_t4)C++17
100 / 100
313 ms27584 KiB
#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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...