本文主要是介绍导游的魔棒，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
小C“五一”节参加了五星旅行社组织的一次外出旅游，这次旅游中，小C遇到一件非常有趣的事: 五星旅行社的导游小张有一根魔棒，这根魔棒在每一次的旅游中可以产生一次魔力（也只能产生一次魔力），这魔力可以使两个景点间的距离减成原来的一半。小C在“五一”节的这次旅游中，很有幸是小张导游作为他们的导游，小张当然也没有忘记带他的魔棒，因为他可以发挥魔棒的作用，使路程减少呢。这次旅游中，去了一个有N个景点的旅游区，这个旅游区只有一个入口，在景点编号为1的地方，一个出口，在景点编号为N的地方，景点编号为1，2，3，…，N。在入口处有一个N×N的数据阵，描述了景点间的距离，a[I,j]表示景点i到景点j的距离。因为小C的公司有急事要小C尽快回来，现在小C要用张导游的魔棒，使得从入口到出口的距离最短。现在我们也来编一个程序：求将哪一条边减半后使从顶点1到顶点N的最短路径长度最短，输出这个最短距离，如果找不到从1到N的路径，则输出 -1 。
Input
从文件中c.in读入数据，文件第一行是一个正整数N（3 ≤ N ≤ 50），表示共有N个点，接下来是一个N行N列的数据阵，a[I,j]的值表示顶点i到顶点j的长度。
Output
只有一个数就是将一条边长减半后的从1到N的最短路径长度，结果四舍五入到小数后两位，如果找不到从1到N的路径，则输出 -1 。
Sample Input
3
0 5 20
5 0 8
20 8 0
Sample Output
9.00
.
.
.
.
.
分析
a[i][j][0/1]表示i走到j 没用/用了 将边减半的最短距离
然后floyd
.
.
.
.
.
程序：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;int n;
double a[100][100][2];int main()
{freopen("c.in","r",stdin);freopen("c.out","w",stdout);scanf("%d",&n);for (int i=1;i<=n;i++)for (int j=1;j<=n;j++){double x;scanf("%lf",&x);if (x==0) a[i][j][0]=a[i][j][1]=2147483647; else {a[i][j][0]=x;a[i][j][1]=x/2;}}for (int k=1;k<=n;k++)for (int i=1;i<=n;i++)for (int j=1;j<=n;j++){a[i][j][0]=min(a[i][j][0],a[i][k][0]+a[k][j][0]);a[i][j][1]=min(a[i][j][1],a[i][k][1]+a[k][j][0]);a[i][j][1]=min(a[i][j][1],a[i][k][0]+a[k][j][1]);}if (a[1][n][1]!=2147483647) printf("%0.2lf",a[1][n][1]); else printf("-1");fclose(stdin);fclose(stdout);return 0;
}
这篇关于导游的魔棒的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
