题目描述:
给出一个有 n 个顶点的有向网,指定其中 k 个顶点( 不含顶点 1 和顶点 n ),求从顶点 1 到顶点 n 的,经过那 k 个顶点的最短路。
输入:
第一行是 顶点数 n 和 弧数目 e 。 1 ≤ n ≤ 40 ,1 ≤ e ≤ n × n
接下来是 e 行,每行三个整数 i , j , v ( 其中 0 < i, j ≤ n , 0 < v ≤ 100 ) ,表示从 顶点 i 到 顶点 j 的一条权值为 v 的弧。
接下来是一个正整数 k ( 1 ≤ k ≤ n - 2 ),接下来是 k 个正整数,表示必须经过的 k 个顶点。输出:
如果不存在满足条件的路径,输出一行 "No solution";
否则,输出两行:
第 1 行,该最短路的长度;
第 2 行从顶点 1 到顶点 n 的最短路,顶点之间用一个空格分隔,要求按路径的顶点次序,前一个顶点必须有弧指向后一个顶点
思路:暴力枚举所有满足条件的路径,计算路径长度并不断更新最短距离值。
算法实现:
1.跑一遍Floyd,求各顶点之间的最短路径
2.对所有指定点进行全排列,对每个排列计算:顶点1到序列首顶点的距离+序列中相邻顶点之间的距离+序列末顶点到顶点n的距离,并不断更新得到最短路径
3.特判不存在满足路径的情况
代码如下:
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f //设无穷大值
int n, m, k, idx;
int dist[45][45]; //存储各顶点间的最短路
int path[45][45]; //用于floyd存储路径
int must[40]; //存储指定点序列
char temp[45], anspath[45];
void floyd() {
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = k;
}
}
//获取点a到点b最短路的中间路径(路径中不含a,b)
void getpath(int a, int b) {
if (path[a][b] == -1)
return;
else {
int k = path[a][b];
getpath(a, k);
anspath[idx++] = k;
getpath(k, b);
}
}
//将“点1沿着当前must数组中指定点的顺序走到点n的路径”保存到anspath数组
void savpath() {
anspath[idx++] = 1;
getpath(1, must[0]);
for (int i = 0; i < k - 1; i++) {
anspath[idx++] = must[i];
getpath(must[i], must[i + 1]);
}
anspath[idx++] = must[k - 1];
getpath(must[k - 1], n);
anspath[idx++] = n;
}
//返回 点1沿着当前must数组中指定点的顺序走到点n 的路径长度
int getdis() {
int distance = dist[1][must[0]];
if (dist[1][must[0]] == INF)
return INF + 1;
for (int i = 0; i < k - 1; i++) {
if (dist[must[i]][must[i + 1]] == INF)
return INF + 1;
distance += dist[must[i]][must[i + 1]];
}
if (dist[must[k - 1]][n] == INF)
return INF + 1;
distance += dist[must[k - 1]][n];
return distance;
}
int main() {
memset(dist, 0x3f, sizeof dist);
memset(path, -1, sizeof path);
scanf("%d%d", &n, &m);
int a, b, w;
while (m--) {
scanf("%d%d%d", &a, &b, &w);
dist[a][b] = min(dist[a][b], w);
}
floyd();
scanf("%d", &k);
for (int i = 0; i < k; i++)
scanf("%d", &must[i]);
//判断点1能否走到点n
if (dist[1][n] == INF) {
printf("No solution\n");
return 0;
}
//使用next_permutation函数前先对数组进行排序
sort(must, must + k);
int mindis = INF;
do {
int d = getdis();
if (mindis > d) {//如果存在更短的路径则更新答案,并把路径存到anspath[]
mindis = d;
idx = 0;
savpath();
}
} while (next_permutation(must, must + k));
printf("%d\n", mindis);
for (int i = 0; i < idx; i++)
printf("%d ", anspath[i]);
return 0;
}
本题的一个坑:使用dfs算法无法通过。
如果通过使用dfs算法记录所有点1到达点n并且经过指定点的路径,在其中取最小值并不正确。因为dfs算法要求路径中的点最多只出现一次,但经过指定点的最短路的路径中可能存在同一个点出现多次的情况,而这种情况恰好被dfs排除,因此本题不用dfs。
例:在如下图中,求点1经过点2,点3到达点4的最短路径和长度
如果我们用dfs求解,得到的最短路径为:1->2->3->4,长度为420
而用暴力方法得到的最短路答案为:1->2->3->2->4,长度为40,其中点2在路径中出现过两次文章来源:https://www.toymoban.com/news/detail-604012.html
显然,后者所求的最短路径正确文章来源地址https://www.toymoban.com/news/detail-604012.html
到了这里,关于经过指定点的最短路径的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!