转载注明出自bestsort.cn,谢谢合作

分层图最短路

应用场景

分层图最短路在最短路的基础上,增加了一个条件:可将 n 条边的权值变为 0. 比如说下图: 那么最短路肯定是如下图但是如果我们能把一条边的权值变为 0 的话,最短路应该是下面这个样子而分层图就是用来解决这类问题的. 仔细回想下最短路的 floyd 算法,每次对于一个点 k ,用 $dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j])$ 来择优选择.这里的分层图也是一样的道理,每次对 此条边免费 和 此条边不免费 进行 DP,最终结果便是最优解. 设会有 K 次免费机会,则 dis的状态转移方程为: $dis[i][j]=min(dis[father][j-1],dis[father][j]+w)$ 其中, $father$ 表示节点 $i$ 的父亲节点, $w$ 表示节点 $i$ 到 $j$ 的边权.当 $j-1>=k$ 时, $dis[father][j]=INF$ ( $INF$ 为无穷大,通常用0x3f3f3f3f表示) 事实上，这个 DP 就相当于把每个结点拆分成了 $k+1$ 个结点，每个新结点代表使用不同多次免费通行后到达的原图结点。换句话说，就是每个结点 $u[i]$ 表示使用 i 次免费通行权限后到达 $u$ 结点。在代码实现里面,核心代码只不过在最短路的基础上修改了几行用于 DP,代码本身并不难.

这里代码中的最短路部分采用的算法是 **Dijkstra+堆优化

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <list>
#include <cstring>
#include <map>
#include <limits>
#include <cmath>
#define IN freopen("in.txt","r",stdin);
using namespace std;
typedef long long int ll;
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;

struct State
{                  // 优先队列的结点结构体
    int v, w, cnt; // cnt 表示已经使用多少次免费通行权限
    State() {}
    State(int v, int w, int cnt) : v(v), w(w), cnt(cnt) {}
    bool operator<(const State &rhs) const { return w > rhs.w; }
};
struct node
{
    int v;
    int w;
    int next;
    /* data */
}edge[maxn];
priority_queue<State>pq;
int n,t,m,k,u,v,w,s;
int cnt;
bool vis[maxn][20];
int dis[maxn][20];
int head[maxn];

void add(int u,int v,int w){    //链式前向星存边
    edge[cnt] = {v,w,head[u]};
    head[u] = cnt++;
}

void dijkstra()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[s][0] = 0;
    pq.push(State(s, 0, 0)); // 到起点不需要使用免费通行权，距离为零
    while (!pq.empty())
    {
        State top = pq.top();
        pq.pop();
        int u = top.v;
        int nowCnt = top.cnt;
        if (vis[u][nowCnt])
            continue;
        vis[u][nowCnt] = true;

        for (int i = head[u]; ~i; i = edge[i].next)
        {
            int v = edge[i].v, w = edge[i].w;
            if (nowCnt < k && dis[v][nowCnt + 1] > dis[u][nowCnt])
            { // 可以免费通行
                dis[v][nowCnt + 1] = dis[u][nowCnt];
                pq.push(State(v, dis[v][nowCnt + 1], nowCnt + 1));
            }
            if (dis[v][nowCnt] > dis[u][nowCnt] + w)
            { // 不可以免费通行
                dis[v][nowCnt] = dis[u][nowCnt] + w;
                pq.push(State(v, dis[v][nowCnt], nowCnt));
            }
        }
    }
}

int main()
{
    //IN;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(head,-1,sizeof (head));
    cin >> n >> m >> k;
    cin >> s >> t;
    while (m--)
    {
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w); 
    }
    int ans = INF;
    dijkstra();
    for (int i = 0; i <= k; ++i)
        ans = min(ans, dis[t][i]); // 对到达终点的所有情况取最优值
    cout << ans << endl;
}
复制