第13回日本情報オリンピック　本選 D - フクロモモンガ （Sugar Glider） 题解

题目链接：D - フクロモモンガ （Sugar Glider）

题目大意：有 \(n\) 棵树和一只猴子，每一棵树有一个高度 \(h_i\) ，有 \(m\) 棵树之间可以互相飞行，花费时间是 \(t_i\) ，并且在飞行过程中，每过一个单位时间高度会下降 \(1\) ，你在到达一棵树时的高度不能大于这棵树的高度也不能小于零，猴子在一棵树上可以花费一个单位的时间使自己的高度增加 \(1\) 或减少 \(1\) ，猴子一开始在第一棵树高度为 \(X\) 处，问若要爬到第 \(n\) 棵树的最高处最少要花费多长时间。

\(n\leq 10^5,m\leq 3\cdot 10^5,h_i,t_i,X\leq 10^9\)

Subtask 1: \(n,m \leq 100,h_i\leq 1000\) (25 points)

Subtask 2: \(X=0\) (25 points)

题解：考虑 \(X=0\) 时的弱化版，显然我们可以令到达每一棵树的时候高度都是零，容易证明这样是不劣的，然后考虑 \(X\) 不为 \(0\) 的情况，因为前面的若干步每一步都会导致高度下降 \(1\) ，所以我们求出每一个点的最短路动态计算边权即可。

使用 Dijkstra 算法跑最短路，时间复杂度 \(O(n\log m)\)。

代码：

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int Maxn=100000;
const int Maxm=300000;
const ll Inf=0x3f3f3f3f3f3f3f3fll;
int n,m,x;
int head[Maxn+5],arrive[Maxm<<1|5],nxt[Maxm<<1|5],val[Maxm<<1|5],tot;
int h[Maxn+5];
void add_edge(int from,int to,int w){
    arrive[++tot]=to;
    nxt[tot]=head[from];
    val[tot]=w;
    head[from]=tot;
}
ll dis[Maxn+5];
priority_queue,vector >,greater > > q;
void dij(int s){
    memset(dis,0x3f,sizeof dis);
    dis[s]=0;
    q.push(make_pair(0ll,s));
    while(!q.empty()){
        pair u=q.top();
        q.pop();
        if(u.first!=dis[u.second]){
            continue;
        }
        for(int i=head[u.second];i;i=nxt[i]){
            int v=arrive[i];
            if(h[u.second]-val[i]<0){
                continue;
            }
            ll tmp_dis;
            if(max(0ll,x-dis[u.second])-val[i]>h[v]){
                tmp_dis=x-dis[u.second]-h[v];
            }
            else{
                tmp_dis=val[i]+max(0ll,val[i]-max(0ll,x-dis[u.second]));
            }
            tmp_dis+=dis[u.second];
            if(tmp_dis=Inf){
        puts("-1");
    }
    else{
        printf("%lld\n",dis[n]+h[n]-max(0ll,x-dis[n]));
    }
    return 0;
}