免费咨询热线_广告优化师培训_无锡网站建设方案优化_站内优化

单源最短路的扩展和变形：

• 分层图
• 拆点
• 计数（最短路个数的计数）
• 多个起点
• 如何求次短路

1137. 选择最佳线路

有一天，琪琪想乘坐公交车去拜访她的一位朋友。

由于琪琪非常容易晕车，所以她想尽快到达朋友家。

现在给定你一张城市交通路线图，上面包含城市的公交站台以及公交线路的具体分布。

已知城市中共包含 $n$ 个车站（编号$1$~$n$）以及 $m$ 条公交线路。

每条公交线路都是 单向的，从一个车站出发直接到达另一个车站，两个车站之间可能存在多条公交线路。

琪琪的朋友住在 $s$ 号车站附近。

琪琪可以在任何车站选择换乘其它公共汽车。

请找出琪琪到达她的朋友家（附近的公交车站）需要花费的最少时间。

输入格式

输入包含多组测试数据。

每组测试数据第一行包含三个整数 $n,m,s$ 分别表示车站数量，公交线路数量以及朋友家附近车站的编号。

接下来 $m$ 行，每行包含三个整数 $p,q,t$ 表示存在一条线路从车站 $p$ 到达车站 $q$，用时为 $t$。

接下来一行，包含一个整数 $w$，表示琪琪家附近共有 $w$ 个车站，她可以在这 $w$ 个车站中选择一个车站作为始发站。

再一行，包含 $w$ 个整数，表示琪琪家附近的 $w$ 个车站的编号。

输出格式

每个测试数据输出一个整数作为结果，表示所需花费的最少时间。

如果无法达到朋友家的车站，则输出 -1。

每个结果占一行。

数据范围

$n\le 1000,m\le 20000$,
$1\le s\le n$,
$0<w<n$,
$0<t\le 1000$

输入样例：

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

输出样例：

1
-1

思路：

• 这个题目可以看作是多个起点，一个终点，求出某一个起点到达该终点的最短路径，可以进行反向建边，求从终点走到所有起点中的最短路径，但是这样扩展性不好，如果出现多个起点，多个终点，求多个起点到多个终点中的最短路径就难以运用和扩展
• 假想一个虚拟源点，从虚拟源点向源点出发连接一条权值为 $0$ 的边，问题变成从虚拟源点到终点的最短距离

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010, M = 21000;
int n, m, s, h[N], e[M], ne[M], w[M], idx, dist[N], ww;
bool st[N];
int p, q, t;void add(int p, int q, int t){e[idx] = q;w[idx] = t;ne[idx] = h[p];h[p] = idx++;
}void spfa(){memset(dist, 0x3f, sizeof dist);dist[0] = 0;queue<int> q;q.push(0);st[0] = true;while(q.size()){int ver = q.front();q.pop();st[ver] = false;for (int i = h[ver]; ~i; i = ne[i]){int j = e[i];if(dist[j] > dist[ver] + w[i]){dist[j] = dist[ver] + w[i];if(!st[j]) {q.push(j);st[j] = true;}}}}printf("%d\n", (dist[s] == 0x3f3f3f3f ? -1 : dist[s]));
}int main(){while(scanf("%d%d%d", &n, &m, &s) != EOF){memset(h, -1, sizeof h);idx = 0;while(m--){scanf("%d%d%d", &p, &q, &t);add(p, q, t);}scanf("%d", &ww);while(ww--){scanf("%d", &t);add(0, t, 0); // 0为虚拟源点}spfa();}return 0;
}

需要注意的是：由于新添加了边（虚拟源点到起点的边），因此边的最大数量需要开大点，至少是 $max(m+s)$

1131. 拯救大兵瑞恩

1944 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。

瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。

迷宫的外形是一个长方形，其南北方向被划分为 $N$ 行，东西方向被划分为 $M$ 列， 于是整个迷宫被划分为 $N\times M$ 个单元。

每一个单元的位置可用一个有序数对 (单元的行号, 单元的列号) 来表示。

南北或东西方向相邻的 $2$ 个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。

注意： 门可以从两个方向穿过，即可以看成一条无向边。

迷宫中有一些单元存放着钥匙，同一个单元可能存放 多把钥匙，并且所有的门被分成 $P$ 类，打开同一类的门的钥匙相同，不同类门的钥匙不同。

大兵瑞恩被关押在迷宫的东南角，即 $(N,M)$ 单元里，并已经昏迷。

迷宫只有一个入口，在西北角。

也就是说，麦克可以直接进入 $(1,1)$ 单元。

另外，麦克从一个单元移动到另一个相邻单元的时间为 $1$，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。

试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。

输入格式

第一行有三个整数,分别表示 $N,M,P$ 的值。

第二行是一个整数 $k$，表示迷宫中门和墙的总数。

接下来 $k$ 行，每行包含五个整数，$X_{i1},Y_{i1},X_{i2},Y_{i2},G_i$：当 $G_i\ge 1$ 时，表示 $(X_{i1},Y_{i1})$ 单元与 $(X_{i2},Y_{i2})$ 单元之间有一扇第 $G_i$ 类的门，当 $G_i=0$ 时，表示 $(X_{i1},Y_{i1})$ 单元与 $(X_{i2},Y_{i2})$ 单元之间有一面不可逾越的墙。

接下来一行，包含一个整数 $S$，表示迷宫中存放的钥匙的总数。

接下来 $S$ 行，每行包含三个整数 $X_{i1},Y_{i1},Q_i$，表示 $(X_{i1},Y_{i1})$ 单元里存在一个能开启第 $Q_i$ 类门的钥匙。

输出格式

输出麦克营救到大兵瑞恩的最短时间。

如果问题无解，则输出 -1。

数据范围

$|X_{i}1-X_{i}2|+|Y_{i}1-Y_{i}2|=1$,
$0\le G_i\le P$,
$1\le Q_i\le P$,
$1\le N,M,P\le 10$,
$1\le k\le 150$

输入样例：

4 4 9
9
1 2 1 3 2
1 2 2 2 0
2 1 2 2 0
2 1 3 1 0 
2 3 3 3 0
2 4 3 4 1
3 2 3 3 0
3 3 4 3 0
4 3 4 4 0
2
2 1 2 
4 2 1

输出样例：

14

样例解释：

迷宫如下所示：

思路：

• 动态规划分析：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <deque>
#include <set>#define x first
#define y secondusing namespace std;typedef pair<int, int> PII;const int N = 11, M = 360, P = 1 << 10;int n, m, k, p;
int h[N * N], e[M], w[M], ne[M], idx;
int g[N][N], key[N * N];
int dist[N * N][P];
bool st[N * N][P];set<PII> edges;void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}void build()
{int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )for (int u = 0; u < 4; u ++ ){int x = i + dx[u], y = j + dy[u];if (!x || x > n || !y || y > m) continue;int a = g[i][j], b = g[x][y];if (!edges.count({a, b})) add(a, b, 0);}
}int bfs()
{memset(dist, 0x3f, sizeof dist);dist[1][0] = 0;deque<PII> q;q.push_back({1, 0});while (q.size()){PII t = q.front();q.pop_front();if (st[t.x][t.y]) continue;st[t.x][t.y] = true;if (t.x == n * m) return dist[t.x][t.y];if (key[t.x]){int state = t.y | key[t.x];if (dist[t.x][state] > dist[t.x][t.y]){dist[t.x][state] = dist[t.x][t.y];q.push_front({t.x, state});}}for (int i = h[t.x]; ~i; i = ne[i]){int j = e[i];if (w[i] && !(t.y >> w[i] - 1 & 1)) continue;   // 有门并且没有钥匙if (dist[j][t.y] > dist[t.x][t.y] + 1){dist[j][t.y] = dist[t.x][t.y] + 1;q.push_back({j, t.y});}}}return -1;
}int main()
{cin >> n >> m >> p >> k;for (int i = 1, t = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )g[i][j] = t ++ ;memset(h, -1, sizeof h);while (k -- ){int x1, y1, x2, y2, c;cin >> x1 >> y1 >> x2 >> y2 >> c;int a = g[x1][y1], b = g[x2][y2];edges.insert({a, b}), edges.insert({b, a});if (c) add(a, b, c), add(b, a, c);}build();int s;cin >> s;while (s -- ){int x, y, c;cin >> x >> y >> c;key[g[x][y]] |= 1 << c - 1;}cout << bfs() << endl;return 0;
}

1134. 最短路计数

给出一个 $N$ 个顶点 $M$ 条边的无向无权图，顶点编号为 $1$ 到 $N$。

问从顶点 $1$ 开始，到其他每个点的最短路有几条。

输入格式

第一行包含 $2$ 个正整数 $N,M$ 为图的顶点数与边数。

接下来 $M$ 行，每行两个正整数 $x,y$ 表示有一条顶点 $x$ 连向顶点 $y$ 的边，请注意可能有自环与重边。

输出格式

输出 $N$ 行，每行一个非负整数，第 $i$ 行输出从顶点 $1$ 到顶点 $i$ 有多少条不同的最短路，由于答案有可能会很大，你只需要输出对 $100003$ 取模后的结果即可。

如果无法到达顶点 $i$ 则输出 $0$。

数据范围

$1\le N\le 10^5$,
$1\le M\le 2\times 10^5$

输入样例：

5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5

输出样例：

1
1
1
2
4

思路：

• 设 $cn{t}_i$ 表示 $1\sim i$ 的最短路数量
• 对于每次 SPFA 的松弛操作中的每条边 $(a,b,w)$，我们分类讨论：
• 若 $dis{t}_b>dis{t}_a+w$，则 $cn{t}_b$ 应更新为 $cn{t}_a$，因为以前的 $cn{t}_b$ 不是最短路了。
• 若 $dis{t}_b=dis{t}_a+w$，则 $cn{t}_b$ 应加上 $cn{t}_a$，因为这里的最短路长度相同。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;const int N = 100010, M = 400010, mod = 100003;
int n, m, h[N], e[M], ne[M], idx, dist[N], cnt[N];void add(int x, int y){e[idx] = y;ne[idx] = h[x];h[x] = idx++;
}void bfs(){memset(dist, 0x3f, sizeof dist);dist[1] = 0;cnt[1] = 1;queue<int> q;q.push(1);while(q.size()){int ver = q.front();q.pop();for (int i = h[ver]; ~i; i = ne[i]){int j = e[i];if(dist[j] > dist[ver] + 1){dist[j] = dist[ver] + 1;cnt[j] = cnt[ver];q.push(j);}else if(dist[j] == dist[ver] + 1){cnt[j] = (cnt[j] + cnt[ver]) % mod;}}}
}int main(){memset(h, -1, sizeof h);scanf("%d%d", &n, &m);while(m--){int x, y;scanf("%d%d", &x, &y);add(x, y);add(y, x);}bfs();for (int i = 1; i <= n; i++){printf("%d\n", cnt[i]);}return 0;
}

383. 观光

“您的个人假期”旅行社组织了一次比荷卢经济联盟的巴士之旅。

比荷卢经济联盟有很多公交线路。

每天公共汽车都会从一座城市开往另一座城市。

沿途汽车可能会在一些城市（零或更多）停靠。

旅行社计划旅途从 $S$ 城市出发，到 $F$ 城市结束。

由于不同旅客的景点偏好不同，所以为了迎合更多旅客，旅行社将为客户提供多种不同线路。

游客可以选择的行进路线有所限制，要么满足所选路线总路程为 $S$ 到 $F$ 的最小路程，要么满足所选路线总路程仅比最小路程多一个单位长度。

如上图所示，如果 $S=1，F=5$ 则这里有两条最短路线 $1\to 2\to 5,1\to 3\to 5$ 长度为 $6$；有一条比最短路程多一个单位长度的路线 $1\to 3\to 4\to 5$ 长度为 $7$。

现在给定比荷卢经济联盟的公交路线图以及两个城市 $S$ 和 $F$，请你求出旅行社最多可以为旅客提供多少种不同的满足限制条件的线路。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含两个整数 $N$ 和 $M$，分别表示总城市数量和道路数量。

接下来 $M$ 行，每行包含三个整数 $A,B,L$ 表示有一条线路从城市 $A$ 通往城市 $B$，长度为 $L$。

需注意，线路是 单向的，存在从 $A$ 到 $B$ 的线路不代表一定存在从 $B$ 到 $A$ 的线路，另外从城市 $A$ 到城市 $B$ 可能存在多个不同的线路。

接下来一行，包含两个整数 $S$ 和 $F$，数据保证 $S$ 和 $F$ 不同，并且 $S、F$ 之间至少存在一条线路。

输出格式

每组数据输出一个结果，每个结果占一行。

数据保证结果不超过 $10^9$。

数据范围

$2\le N\le 1000$,
$1\le M\le 10000$,
$1\le L\le 1000$，
$1\le A,B,S,F\le N$

输入样例：

2
5 8
1 2 3
1 3 2
1 4 5
2 3 1
2 5 3
3 4 2
3 5 4
4 5 3
1 5
5 6
2 3 1
3 2 1
3 1 10
4 5 2
5 2 7
5 2 7
4 1

输出样例：

3
2

思路：

• 次短路径：如果存在比最短路径长度恰好多 $1$ 的路径，则再把这样的路径条数加上
• 此题和前一题类似，只要多统计一下次短路的数量即可。
• 更新次短路时和更新最大值的代码类似。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 1010, M = 10010;
struct Ver{int ver, type, dist; // type表示类型，即最短路还是次短路bool operator> (const Ver &W) const{return dist > W.dist;}
};
int t, n, m, h[N], ne[M], e[M], w[M], idx, dist[N][2], cnt[N][2], S, T;
bool st[N][2];void add(int x, int y, int z){w[idx] = z;e[idx] = y;ne[idx] = h[x];h[x] = idx++;
}void dijkstra(){memset(st, false, sizeof st);memset(cnt, 0, sizeof cnt);memset(dist, 0x3f, sizeof dist);dist[S][0] = 0, cnt[S][0] = 1;priority_queue<Ver, vector<Ver>, greater<Ver>> q;q.push({S, 0, 0});while(q.size()){Ver t = q.top();q.pop();int ver = t.ver, type = t.type, dis = t.dist, count = cnt[ver][type];if(st[ver][type]) continue;st[ver][type] = true;for (int i = h[ver]; ~i; i = ne[i]){int j = e[i];if(dist[j][0] > dis + w[i]){ // 如果找到了更短的最短距离dist[j][1] = dist[j][0], cnt[j][1] = cnt[j][0];q.push({j, 1, dist[j][1]});dist[j][0] = dis + w[i], cnt[j][0] = count;q.push({j, 0, dist[j][0]});}else if(dist[j][0] == dis + w[i]) cnt[j][0] += count; // 如果有相同的最短距离else if(dist[j][1] > dis + w[i]){ // 如果找到了更短的次短距离dist[j][1] = dis + w[i], cnt[j][1] = count;q.push({j, 1, dist[j][1]});}else if(dist[j][1] == dis + w[i]) cnt[j][1] += count;  // 如果有相同的次短距离}}int res = cnt[T][0];if(dist[T][0] + 1 == dist[T][1]) res += cnt[T][1];printf("%d\n", res);
}int main(){scanf("%d", &t);while(t--){memset(h, -1, sizeof h);idx = 0;scanf("%d%d", &n, &m);while(m--){int x, y, z;scanf("%d%d%d", &x, &y, &z);add(x, y, z);}scanf("%d%d", &S, &T);dijkstra();}return 0;
}