【floyed】导游的魔棒

导游的魔棒"/>

【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]);
}