Catalog
  1. 1. ARX:我今天上午做了两个分层图最短路的题,可简单了……
  • 概念
  • 算法思路
  • 算法细节
  • 分层图最短路-学习
    ARX:我今天上午做了两个分层图最短路的题,可简单了……

    概念

    分层图最短路是指在可以进行分层图的图上解决最短路问题。
    一般模型是:
    在图上,有k次机会可以直接通过一条边,问起点与终点之间的最短路径。

    算法思路

    这是一个类似于DP的思路。
    用直接通过的边把整个图分成k个子图,其中k为可以直接通过的边的个数。在此基础上,我们直接跑最短路算法就可以了。

    算法细节

    在处理子图与子图之间的关系时,由于连接两个子图的路径是可以直接通过的,所以我们在记录下一层的路径长度时,转移方程为:
    if(d[edge[i].to][level + 1] < d[u][level] && level < k) d[edge[i].to][level + 1] = d[u][level];
    其中edge[i]是一条以节点u为起点的边。注意,由于图的层数有限,所以level < k这一条件一定不要忘记加。
    附一下代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<queue>
    #define ll long long
    #define INF 2147483647

    using namespace std;

    struct node{
    int k,dis,used;
    bool operator < ( const node &x )const{return x.dis < dis;}
    };

    priority_queue<node> que;

    long long n,m,k,s,t,d[50005],cnt,D[50005][15],v[50005][15];

    struct Edge{
    int to,next,x;
    }edge[2000005];

    void add(int x,int y,int a)
    {
    edge[++cnt].to = y;
    edge[cnt].x = a;
    edge[cnt].next = d[x];
    d[x] = cnt;
    }

    int main()
    {
    int x,y,a;
    scanf("%lld%lld%lld",&n,&m,&k);
    scanf("%d%d",&s,&t);
    for(register int i = 1; i <= m; i++)
    {
    scanf("%d%d%d",&x,&y,&a);
    add(x,y,a);
    add(y,x,a);
    }
    que.push((node){s,0,0});
    for(register int i = 0; i <= n; i++)
    for(register int j = 0; j <= k; j++)
    D[i][j] = INF;
    D[s][0] = 0;
    while(!que.empty())
    {
    node u = que.top();
    que.pop();
    int kk = u.k,level = u.used;
    if(v[u.k][u.used]) continue;
    v[u.k][u.used] = 1;
    for(register int i = d[kk]; i; i = edge[i].next)
    {

    int too = edge[i].to;
    if(D[too][level] > D[kk][level] + edge[i].x)
    {
    D[too][level] = edge[i].x + D[kk][level];
    que.push((node){too,D[too][level],level});
    }
    if(level < k && D[too][level + 1] > D[kk][level])
    {
    D[too][level + 1] = D[kk][level];
    que.push((node){too,D[too][level + 1],level + 1});
    }
    }
    }
    long long ans = INF;
    for(register int i = 0; i <= k; i++) ans = min(ans,D[t][i]);
    printf("%lld\n",ans);
    return 0;
    }

    推荐练习题目:飞行路线冻结回家的路

    Author: wflight
    Link: http://yoursite.com/2019/08/02/分层图最短路-学习/
    Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
    Donate
    • 微信
    • 支付寶

    Comment