CCPC-Wannafly Winter Camp Day1 (Div2, onsite) F 爬爬爬山 最短路

F-爬爬爬山

第一座山的高度确定了，R[1]。当前体力为k，山与山之间的边权为w。那么当后面山的高度大于R[1]+k的时候就需要将山的高度降低。上山消耗体力，下山增加体力，其实就相同高度低于R[1]的时候这个山不存在。因为如果碰到了一个在高的山，增加的体力就被抵消了，相同于没有。那就将边权加上多出来的那部分，（R[x]-（R[1]+k）)^2，然后跑最短路就行了。

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const long long inf=0x3f3f3f3f3f3f3f3f;
long long dis[maxn];
bool vis[maxn];
struct node{
    int u;
    long long dis;
    bool operator < (const node &r)const{
        return dis>r.dis;
    }
};
struct edge{
    int v;
    long long w;
    int next;
}e[maxn*10];
int head[maxn*10],hcnt=0;
int n,m,k;
void add(int u,int v,long long int w){
    e[hcnt]=edge{v,w,head[u]};
    head[u]=hcnt++;
}
void dij(int start){
    priority_queue<node> que;
    for(int i=1;i<=n;i++)
        vis[i]=false,dis[i]=inf;
    que.push({start,0});
    dis[start]=0;
    while(!que.empty()){
        int u=que.top().u;
        que.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];i>=0;i=e[i].next){
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w)
            dis[v]=dis[u]+e[i].w,que.push({v,dis[v]});
        }
    }
}
long long int r[maxn];
int main(){
    memset(head,-1,sizeof(head));
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)scanf("%lld",&r[i]);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w+max(0LL,r[v]-(r[1]+k))*max(0LL,r[v]-(r[1]+k)));
        add(v,u,w+max(0LL,r[u]-(r[1]+k))*max(0LL,r[u]-(r[1]+k)));
    }
    dij(1);
    printf("%lld\n",dis[n]);
    return 0;
}