题目描述
Alice 和 Bob 现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在 (n) 个城市设有业务，设这些城市分别标记为 (0) 到 (n−1)，一共有 (m) 种航线，每种航线连接两个城市，并且航线有一定的价格。
Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多 (k) 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少？
-
输入格式 第一行三个整数 (n,m,k) 分别表示城市数，航线数和免费乘坐次数。
接下来一行两个整数 (s,t)，分别表示他们出行的起点城市编号和终点城市编号。
接下来 (m) 行，每行三个整数 (a,b,c)，表示存在一种航线，能从城市 (a) 到达城市 (b)，或从城市 (b) 到达城市 (a)，价格为 (c)。 -
输出格式 输出一行一个整数，为最少花费。
样例输入
5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100
样例输入
8
分析
分层图。。。
各层内部正常连边，各层之间从上到下连权值为0的边。每向下跑一层，就相当于免费搭一次飞机。跑一遍从 (s) 到 (t+n∗k) 的最短路即可。
AC代码
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
struct edge {
int to, next, weight;
} a[6000060];
struct node {
int dist, id;
node() {}
node(int dist, int id) : dist(dist), id(id) {}
};
bool operator<(node xi, node yi) { return xi.dist > yi.dist; }
int n, m, k;
int s, t;
int x, y, w;
int cnt(0);
int head[1000010];
int vis[1000010];
int dist[1000010];
void addedge(int xi, int yi, int wi) {
a[cnt].to = yi;
a[cnt].next = head[xi];
a[cnt].weight = wi;
head[xi] = cnt++;
}
void dijkstra(int s) {
memset(vis, 0, sizeof(vis));
memset(dist, INF, sizeof(dist));
priority_queue<node> q;
q.push(node(0, s));
dist[s] = 0;
while (!q.empty()) {
node t(q.top());
q.pop();
if (vis[t.id])
continue;
vis[t.id] = 1;
for (int i = head[t.id]; i != -1; i = a[i].next) {
int v = a[i].to;
if (dist[v] > a[i].weight + t.dist) {
dist[v] = a[i].weight + t.dist;
q.push(node(dist[v], v));
}
}
}
}
int main() {
memset(head, -1, sizeof(head));
scanf("%d%d%d", &n, &m, &k);
scanf("%d%d", &s, &t);
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &x, &y, &w);
addedge(x, y, w);
addedge(y, x, w);
for (int j = 1; j <= k; j++) {
addedge(x + (j * n), y + (j * n), w);
addedge(y + (j * n), x + (j * n), w);
addedge(x + ((j - 1) * n), y + (j * n), 0);
addedge(y + ((j - 1) * n), x + (j * n), 0);
}
}
for (int i = 1; i <= k; i++) addedge(t + (i - 1) * n, t + i * n, 0);
dijkstra(s);
printf("%d", dist[t + k * n]);
return 0;
}