AOJ0601 フクロモモンガ(Sugar Glider)

問題

Sugar Glider | Aizu Online Judge

解法

負の高さへもいくらでも降りれるとして、最後に元来登らなければいけない秒数を足してしまうとすれば、となるので、高さまで保存しなくて良くなってダイクストラで間に合います。

実装

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int MAX_N = 100000;
 
struct Data
{
    int v, cost;
    Data() {}
    Data(int _v, int _cost)
    {
        v = _v; cost = _cost;
    }
    bool operator < (const Data &d) const
    {
        return cost > d.cost;
    }
};
 
int N, M, X, H[MAX_N];
vector<Data> e[MAX_N];
 
signed main()
{
    cin >> N >> M >> X;
    for (int i = 0; i < N; i++)
    {
        cin >> H[i];
    }
    for (int i = 0; i < M; i++)
    {
        int a, b, t;
        cin >> a >> b >> t;
        a--; b--;
        e[a].push_back(Data(b, t));
        e[b].push_back(Data(a, t));
    }
     
    priority_queue<Data> pq;
    pq.push(Data(0, 0));
    bool isUsed[MAX_N] = {};
    while (!pq.empty())
    {
        Data t = pq.top(); pq.pop();
        if (t.v == N - 1)
        {
            printf("%lld\n", t.cost + (0ll, t.cost + H[N - 1] - X));
            return 0;
        }
        if (isUsed[t.v]) continue;
        isUsed[t.v] = true;
        //printf("%lld, %lld\n", t.v + 1, t.cost);
        for (int i = 0; i < e[t.v].size(); i++)
        {
            Data &_e = e[t.v][i];
            if (H[t.v] < _e.cost) continue;
            pq.push(Data(_e.v, t.cost + _e.cost + max(0ll, max(0ll, X - t.cost - _e.cost) - H[_e.v])));
        }
    }
    puts("-1");
    return 0;
}