CCPC-WannaFly 2018WC Day1 F.爬爬爬山(最短路变形)

题目链接:CCPC-WannaFly 2018WC Day1 F.爬爬爬山

题意:

​ 最短路的变形。
题解:

​ 最短路每次更新时,判断当前体力能不能达到,若不能达到则加上削山的代价后在更新。
参考代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1e17+7;
int n,m,k;
int h[100009];
int cnt=0,fir[100009];
struct Edge
{
    int v,nxt;
    ll w;
} edge[400009];
void addedge(int u,int v,ll w)
{
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].nxt=fir[u];
    fir[u]=cnt++;
}
struct node
{
    int u;
    ll d;
    node(int u,ll d):u(u),d(d) {}
    bool operator < (const node &a) const
    {
        return d>a.d;
    }
};
bool used[100009];
ll dis[100009];
void dijkstra(int st,int ed)
{
    priority_queue<node> que;
    while(!que.empty())
        que.pop();
    for(int i=1; i<=n; i++)
        dis[i]=inf;
    dis[st]=0;
    que.push(node(st,dis[st]));
    memset(used,0,sizeof(used));
    while(!que.empty())
    {
        int u=que.top().u;
        que.pop();
        if(used[u])
            continue;
        used[u]=1;
        for(int i=fir[u]; i!=-1; i=edge[i].nxt)
        {
            int v=edge[i].v;
            ll w=edge[i].w;
            if(h[v]>k)
                w+=1ll*(h[v]-k)*(h[v]-k);
            if(used[v])
                continue;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                que.push(node(v,dis[v]));
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    memset(fir,-1,sizeof(fir));
    for(int i=1;    i<=n;   i++)
        scanf("%d",&h[i]);
    int temp=h[1];
    for(int i=1;    i<=n;   i++)
        h[i]-=temp;
    for(int i=1;    i<=m;   i++)
    {
        int u,v;
        ll w;
        scanf("%d%d%lld",&u,&v,&w);
        addedge(u,v,w);
        addedge(v,u,w);
    }
    dijkstra(1,n);
    printf("%lld\n",dis[n]);
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。