洛谷P4568《飞行路线》

十一月 25, 2018 5430

入门级别的分层图最短路

题目地址
双倍经验

前言

先介绍一下分层图最短路。

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

题目描述

Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在nn个城市设有业务，设这些城市分别标记为00到n-1n−1，一共有mm种航线，每种航线连接两个城市，并且航线有一定的价格。

Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多kk种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？

输入输出格式

输入格式

数据的第一行有三个整数，n,m,k，分别表示城市数，航线数和免费乘坐次数。

第二行有两个整数，s,t，分别表示他们出行的起点城市编号和终点城市编号。

接下来有m行，每行三个整数，a,b,c，表示存在一种航线，能从城市a到达城市b，或从城市b到达城市a，价格为c。

输出格式

只有一行，包含一个整数，为最少花费。

输入输出样例

输入样例#1： 

1
2
3
4
5
6
7
8
5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100

输出样例#1：

1
8

解题思路

这就是分层图最短路的模板
但为什么是省选/NOI-呢

我们用DP的思想来看
设dis[i][j]表示起点到i点在j层的最短路

如何分层？
理解性记忆。
例如本题最多有十层，第k层表示免费了k次的最短路

如何跑最短路？
洛谷卡SPFA，BZOJ不卡SPFA，但是都要注意把空间开大10倍，不然是过不去的（5次TLE的惨痛经验）
在跑 Dijkstra 的时候，我们用了一个pair来存当前到达的点和已走过的路径；这次我们需要多维护一个东西：当前的层数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Node {
	int id; // 当前到达的点
	int weight; // 已走过的路径
	int now; // 当前的层数
	
	Node() {
		id = weight = now = 0;
	}
	
	// 重载运算符，用于优先队列
	bool operator < (const Node &that) const {
		return weight > that.weight;
	}
};

在更新dis的时候，我们需要对这一层的点和下一层的点分别进行更新

1
2
3
4
5
6
7
8
9
if (!vis[to][Floor] && dis[to][Floor] > dis[now][Floor] + edge[e].weight) {
    dis[to][Floor] = dis[now][Floor] + edge[e].weight;
    q.push(NewNode(to, dis[to][Floor], Floor));
}

if (!vis[to][Floor] && Floor + 1 <= K && dis[to][Floor + 1] > dis[now][Floor]) {
    dis[to][Floor + 1] = dis[now][Floor];
    q.push(NewNode(to, dis[to][Floor + 1], Floor + 1));
}

代码实现

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <queue>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)

namespace FastIO {
    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }
    
    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}


namespace Solution {
    const int MAXN = 100000 + 10;
    const int MAXM = 500000 + 10;
    const int MAXK = 10 + 5;
    
    struct Node {
        int id, weight, now;
        Node() {
            id = weight = now = 0;
        }
        bool operator < (const Node &that) const {
            return weight > that.weight;
        }
    } head[MAXN];
    
    struct Edge {
        int now, next, weight;
    } edge[MAXM];
    
    int n, m, k, s, t, K, cnt, dis[MAXN][MAXK];
    bool vis[MAXN][MAXK];
    
    inline void addEdge(int prev, int next, int weight) {
        edge[++cnt].now = next;
        edge[cnt].weight = weight;
        edge[cnt].next = head[prev].id;
        head[prev].id = cnt;
    }
    
    Node NewNode(int id, int weight, int now) {
        Node tmp;
        tmp.id = id;
        tmp.weight = weight;
        tmp.now = now;
        return tmp;
    }
    
    void SPFA() {
        memset(dis, 0x7f, sizeof(dis));
        std::priority_queue<Node> q;
        For (i, 0, K) dis[s][i] = 0;
        q.push(NewNode(s, 0, 0));
        while (!q.empty()) {
            Node NowNode = q.top();
            q.pop();
            int Floor = NowNode.now;
            int now = NowNode.id;
            if (vis[now][Floor]) continue;
            vis[now][Floor] = true;
            for (int e = head[now].id; e; e = edge[e].next) {
                int to = edge[e].now;
                if (!vis[to][Floor] && dis[to][Floor] > dis[now][Floor] + edge[e].weight) {
                    dis[to][Floor] = dis[now][Floor] + edge[e].weight;
                    q.push(NewNode(to, dis[to][Floor], Floor));
                }
                if (!vis[to][Floor] && Floor + 1 <= K && dis[to][Floor + 1] > dis[now][Floor]) {
                    dis[to][Floor + 1] = dis[now][Floor];
                    q.push(NewNode(to, dis[to][Floor + 1], Floor + 1));
                }
            }
        }
    }
}

signed main() {
    using namespace Solution;
    using FastIO::getint;
    n = getint();
    m = getint();
    k = getint();
    s = getint();
    t = getint();
    K = k;
    For (i, 1, m) {
        int prev = getint();
        int next = getint();
        int weight = getint();
        addEdge(prev, next, weight);
        addEdge(next, prev, weight);
    }
    SPFA();
    int ans = 2147482333;
    for (int i = 0; i <= k; ++i) {
        ans = std::min(ans, dis[t][i]);
    }
    FastIO::putint(ans, '\n');
    return 0;
}