Description
Alice 和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务，设这些城市分别标记为0到n-1，一共有m种航线，每 种航线连接两个城市，并且航线有一定的价格。Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推 出优惠，他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？
数据的第一行有三个整数，n,m,k，分别表示城市数，航线数和免费乘坐次数。
第二行有两个整数，s,t，分别表示他们出行的起点城市编号和终点城市编号。(0<=s,t<n)
接下来有m行，每行三个整数，a,b,c，表示存在一种航线，能从城市a到达城市b，或从城市b到达城市a，价格为c。(0<=a,b<n,a与b不相等，0<=c<=1000)
Output
只有一行，包含一个整数，为最少花费。
5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100
Sample Output
8
HINT
对于30%的数据,2<=n<=50,1<=m<=300,k=0;
对于50%的数据,2<=n<=600,1<=m<=6000,0<=k<=1;
对于100%的数据,2<=n<=10000,1<=m<=50000,0<=k<=10.
Solution
很有意思的题目。我们把图复制k成层，第i层表示用了i次优惠券了。那么在相邻层之间的相邻接点连一条权值为0的单向边，跑一遍最短路，答案就是所有层中T的距离最小值。
然后这道题因为初始化把S到T的dis设为INF，所以WA了几次QAQ…大家一定要吸取我的教训呀！
Code
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
| #include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <queue>
#include <map>
using namespace std;
typedef long long LL;
const int INF = 1<<30;
int getint() {
int r = 0, k = 1; char c = getchar();
for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
return r * k;
}
int n, m, k;
int id[20005][15];
int dis[300005];
typedef pair<int, int> pii;
int tot = 0;
priority_queue<pii, vector<pii>, greater<pii> > Q;
struct MagHSK {
int to, next, w;
} edge[5000005];
int cnte = 1, S, T, h[300005];
bool vis[300005];
void ins(int x, int y, int z) {
edge[++cnte].to = y;
edge[cnte].next = h[x];
edge[cnte].w = z;
h[x] = cnte;
}
pii tmp;
int dijkstra() {
int now, ndis;
Q.push(make_pair(0, S));
for (int i = 0; i <= tot; ++i) dis[i] = INF; dis[S] = 0;
while (!Q.empty()) {
tmp = Q.top();
Q.pop();
ndis = tmp.first; now = tmp.second;
if (vis[now]) continue;
vis[now] = true;
for (int i = h[now]; i; i = edge[i].next) {
if (vis[edge[i].to]) continue;
if (dis[edge[i].to] > ndis + edge[i].w) {
dis[edge[i].to] = ndis + edge[i].w;
Q.push(make_pair(dis[edge[i].to], edge[i].to));
}
}
}
int ret = INF;
for (int i = 0; i <= k; ++i) ret = min(ret, dis[id[T][i]]);
return ret;
}
int main() {
n = getint(); m = getint(); k = getint();
for (int i = 0; i <= k; ++i)
for (int j = 1; j <= n; ++j)
id[j][i] = ++tot;
S = getint() + 1; T = getint() + 1;
S = id[S][0];
int x, y, z;
for (int i = 1; i <= m; ++i) {
x = getint() + 1; y = getint() + 1; z = getint();
for (int j = 0; j < k; ++j) {
ins(id[x][j], id[y][j], z);
ins(id[y][j], id[x][j], z);
ins(id[x][j], id[y][j+1], 0);
ins(id[y][j], id[x][j+1], 0);
}
ins(id[x][k], id[y][k], z);
ins(id[y][k], id[x][k], z);
}
int ans = dijkstra();
printf("%d", ans);
return 0;
}
|