「JOI 2014 Final」飞天鼠

显然向上爬是没有必要的，除非会下降到地面以下，才提高到刚好为0。

到达一个点有两种情况：到达高度为0和不为0。

对于高度不为0的情况，显然花费的时间越少高度越高（每下降1m都要1单位时间），而必然高度越高越好，因此只需求花费的最少时间。

对于高度为0的情况，显然花费的时间越少越好。

高度不为0的情况比高度为0的情况要优越，而且事实上，高度不为0的情况花费必然会小于高度为0的情况。因此两种情况可以直接合并。

故可以直接dijkstra跑一遍。

复杂度\(o(mlog(m))\)。

#include<bits/stdc++.h>
#define rep(q,a,b) for(int q=a,q##_end_=b;q<=q##_end_;++q)
#define dep(q,a,b) for(int q=a,q##_end_=b;q>=q##_end_;--q)
#define mem(a,b) memset(a,b,sizeof a )
using namespace std;
typedef long long ll;
char buf[15000000],*p1=buf,*p2=buf;
#define Getchar() p1==p2?EOF:*p1++
void in(int &r) {
    static char c;
    r=0;
    while(c=Getchar(),c<48);
    do r=(r<<1)+(r<<3)+(c^48);
    while(c=Getchar(),c>47);
}
const int mn=100005;
const int mm=300005;
int head[mn],ne[mm<<1],to[mm<<1],cost[mm<<1],cnt1;
#define link_edge(a,b,c) to[++cnt1]=b,ne[cnt1]=head[a],head[a]=cnt1,cost[cnt1]=c
#define travel(x) for(int q(head[x]);q;q=ne[q])
int val[mn];
int n,m;
ll sum[mn];
int H[mn];
bool mark[mn];
struct node {
    ll v;
    int id;
    bool operator <(const node &A)const {
        return v>A.v;
    }
};
priority_queue<node> qw;
void WA(int at) {
    
    rep(q,1,n)sum[q]=1e18;
    qw.push({0,1}),H[1]=at,sum[1]=0;
    ll v;
    while(!qw.empty()) {
        node now=qw.top();
        qw.pop();
        if(mark[now.id])continue;
        mark[now.id]=1;
        int h=H[now.id];
        travel(now.id) {
            if(h-cost[q]>val[to[q]]) {
                v=sum[now.id]+h-cost[q]-val[to[q]]+cost[q];
                if(sum[to[q]]>v) {
                    sum[to[q]]=v;
                    H[to[q]]=val[to[q]];
                    qw.push({sum[to[q]],to[q]});
                }
            } else if(h-cost[q]<0) {
                v=sum[now.id]+cost[q]-h+cost[q];
                if(sum[to[q]]>v) {
                    sum[to[q]]=v;
                    H[to[q]]=0;
                    qw.push({sum[to[q]],to[q]});
                }
            } else {
                if(sum[to[q]]>sum[now.id]+cost[q]) {
                    sum[to[q]]=sum[now.id]+cost[q];
                    H[to[q]]=h-cost[q];
                    qw.push({sum[to[q]],to[q]});
                }
            }
        }
    }
}
int main() {
    p2=buf+fread(buf,1,15000000,stdin);
    int at;
    in(n),in(m),in(at);
    rep(q,1,n)in(val[q]);
    int a,b,c;
    rep(q,1,m) {
        in(a),in(b),in(c);
        if(val[a]>=c)link_edge(a,b,c);
        if(val[b]>=c)link_edge(b,a,c);
    }
    WA(at);
    if(sum[n]==1e18)puts("-1");
    else printf("%lld\n",sum[n]+val[n]-H[n]);
    return 0;
}