本文主要是介绍【floyed】导游的魔棒,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
思路:
初看此题,n<=50直接用floyed写,我用了三维数组f[i][j][0/1]表示从i到j有没有用减半的最短距离,然后floyed来求最短路就好了,然后变量要开double,因为折半要除以2,会出现0.5的情况
C o d e Code Code:
#include <cstdio>
#include <iostream>
#include <cstring>
#define CWH using
#define AK namespace
#define IOI std
CWH AK IOI;
int n;
double a[100][100],f[100][100][100];//a是图
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){scanf("%lf",&a[i][j]); if (a[i][j] == 0) {f[i][j][0] = 10010100;f[i][j][1] = 10010100;}else //要不要折半{ f[i][j][0] = a[i][j];f[i][j][1] = a[i][j] / 2; }}for (int k = 1; k <= n; ++k)//floyedfor (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)if(i != j && i != k && j != k){f[i][j][0] = min (f[i][j][0], f[i][k][0] + f[k][j][0]);f[i][j][1] = min (f[i][j][1], f[i][k][1] + f[k][j][0]);f[i][j][1] = min (f[i][j][1], f[i][k][0] + f[k][j][1]);}if(f[1][n][1] == 10010100)printf("-1");else //判断能否到达 printf("%.2lf",(double)f[1][n][1]);
}
这篇关于【floyed】导游的魔棒的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!