free【分层图最短路】

free

传送门来源: 牛客网

题目描述

Your are given an undirect connected graph.Every edge has a cost to pass.You should choose a path from S to T and you need to pay for all the edges in your path. However, you can choose at most k edges in the graph and change their costs to zero in the beginning. Please answer the minimal total cost you need to pay.

输入描述:

The first line contains five integers n,m,S,T,K.

For each of the following m lines, there are three integers a,b,l, meaning there is an edge that costs l between a and b.

n is the number of nodes and m is the number of edges.

输出描述:

An integer meaning the minimal total cost.

输入

输出

备注:

1≤n,m≤103,1≤S,T,a,b≤n,0≤k≤m,1≤l≤106.

Multiple edges and self loops are allowed.

题目描述：

给出n个点，和m条带权边，并且可以选定几条边令其权值为0，但选择的边数最多是k条，求s和t两点的最短距离。

思路：

有k次机会使边的权值为0，是分层最短路的经典问题。

具体方法看下图：(图中序号是从0开始的，下面讲解用从1开始的)

图源：sugarbliss

根据上图可以知道当k=2时，需要建k+1层的图，其中第一层序号是[1,n]，往下依次是[1+n,n+n]、[1+2n+n+2*n]

在使用链式前向星存图的时候，要同时存下一列的权值，并将上下两层的权值设为0。

最终最短路的长度出现在每一行的最后，即：n、2*n、3*n。

例如（1，5）=10 要存（1+5，5+5）=10、（1+2*5，5+2*5）=1

（1，5+5+1）=0 等。

（看不懂直接看代码很好理解，找了一下午才找了个感觉好适应的板子）

AC代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAX=5e6;

const int INF=0x3f3f3f3f;

LL n,m,s,t,k;

LL head[MAX+5],ans;

LL dis[MAX+5],vis[MAX+5];

struct note{

    LL to;

    LL len;

    LL next;

}edge[MAX+5];

void addedge(LL u,LL v,LL w)

{

    edge[ans].to=v;

    edge[ans].len=w;

    edge[ans].next=head[u];

    head[u]=ans++;

}

void init()

{

    memset(head,-1,sizeof(head));

    ans=0;

}

struct node{

    LL u,len;

    node(LL a,LL b){

        u=b;

        len=a;

    }

    friend bool operator < (node a,node b){

        return a.len>b.len;

    }

};

priority_queue<node>q;

void diji(LL s)

{

    for(LL i=0;i<=(k+1)*n;i++){

        dis[i]=INF;

        vis[i]=0;

    }

    dis[s]=0;

    q.push(node(0,s));

    while(!q.empty()){

        int k=q.top().u;

        q.pop();

        if(vis[k]){

            continue;

        }

        vis[k]=1;

        for(LL i=head[k];~i;i=edge[i].next){

            int t=edge[i].to;

            if((dis[t]>dis[k]+edge[i].len&&edge[i].len!=INF+2)){

                dis[t]=dis[k]+edge[i].len;

                q.push(node(dis[t],t));

            }

        }

    }

}

int main()

{

    scanf("%lld%lld%lld%lld%lld", &n, &m, &s,&t,&k);

    init();

    while(m--)

    {

        LL u, v, w;

        scanf("%lld%lld%lld",&u, &v, &w);

        for(LL i = 0; i <= k; i++)

        {

            addedge(u + i * n, v + i * n, w);

            addedge(v + i * n, u + i * n, w);

            if(i != k)

            {

                addedge(u + i * n, v + (i + 1) * n, 0);

                addedge(v + i * n, u + (i + 1) * n, 0);

            }

        }

    }

    diji(s);

    LL ans = INF;

    for(LL i = 0; i <= k; i++)

        ans = min(ans,dis[t + i * n]);

    printf("%lld\n",ans);

}

巴特西

free【分层图最短路】

free

最新文章

热门文章