JOI2014本選 「フクロモモンガ」
ダイクストラ法なのですが、コストの持ち方を工夫する必要があります。
memo[N] = 累計コスト+(木の高さ-現在位置)
このように持つと、正しくダイクストラ法により解を求めることが出来ます。
木の上下移動は最小限に抑える必要がありますが、木の距離から上下移動が必要かは簡単に調べることが出来るので、pushする前に上下移動が必要かどうかをその都度計算により調べます。
#include <bits/stdc++.h> using namespace std; #define ll long long #define FOR(I,N) for(int I = 0;I<(int)(N);I++) #define P pair<ll,ll> #define pb push_back #define INF 9223372036854775807 struct Node{ vector<P> edges; int at; ll height; Node(int at_,ll height_){ at = at_; height = height_; } Node(){} }; vector<Node> ns; int main(){ int i,j; ll n,m,x,h,a,b,c; cin>>n>>m>>x; FOR(i,n){ cin>>h; ns.pb(Node(i,h)); } FOR(i,m){ cin>>a>>b>>c;a--;b--; ns[a].edges.pb(P(b,c)); ns[b].edges.pb(P(a,c)); } ll memo[100001]; fill_n(memo,100001,INF); priority_queue<P> que; vector<P> alp; alp.pb(P(0,x)); que.push(P(-(ns[0].height-x),alp.size()-1)); ll ans = INF; while(que.size()){ P data = que.top();que.pop(); P data2 = alp[data.second]; ll cost = -data.first; int index = data2.first; ll tx = data2.second; if(memo[index]<=cost)continue; memo[index] = cost; if(index==n-1){ ll tcost = cost-(ns[index].height-tx); ans = min(ans,tcost+ns[index].height-tx); ///break; } FOR(i,ns[index].edges.size()){ int nind = ns[index].edges[i].first; ll distance = ns[index].edges[i].second; ll tcost = cost-(ns[index].height-tx);///本来のコスト ll ncost; ll nx; if(tx-distance<0){///移動後の位置がマイナスになる if(ns[index].height<tx+distance-tx)///高さ足りない continue; ncost = tcost+distance-tx+distance+ns[nind].height-0; nx = 0; }else if(ns[nind].height<tx-distance){///移動後の位置が木の高さ超える ncost = tcost+(tx-distance)-ns[nind].height+distance+0; nx = ns[nind].height; }else{ ncost = tcost+distance+ns[nind].height-(tx-distance); nx = tx-distance; } alp.pb(P(nind,nx)); que.push(P(-ncost,alp.size()-1)); } } if(ans==INF)ans=-1; cout<<ans<<endl; return 0; }