JOI2014本選 「フクロモモンガ」

AOJ0601

ダイクストラ法なのですが、コストの持ち方を工夫する必要があります。

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;
}