zoj1456[通俗易懂]

全栈程序员-站长 • 2022年7月14日下午7:46 • 未分类 • 阅读 14

大家好，又见面了，我是你们的朋友全栈君。

题目大意：

Spring国家有N个城市，每队城市之间也许有运输路线，也可能没有。现在有一些货物要从一个城市运到另一个城市。运输费有两部分组成：
城市之间的运输成本，路过一个城市的税，除了起点和终点城市。
你必须写一个程序找到最小成本的路线
输入：
a11 a12 … a1N
a21 a22 … a2N
……………
aN1 aN2 … aNN
b1 b2 … bN

c d
e f
…
g h
aij是从城市i到城市j的运输成本，aij=-1表明没有直达路线。bi表明路过城市i的税
货物从城市c运到城市d，城市e到城市f

解题思路：

Floyd算法

代码如下：

#include<stdio.h>
#include<iostream>
using namespace std;
#define N 110
#define MAX 9999999
int map[N][N][N];
int g[N][N];
int pre[N][N];
int n;
int cost[N];

void floyd()
{
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=n;j++)
    {
      if(g[i][j]==-1)
        map[0][i][j]=MAX;
      else
        map[0][i][j]=g[i][j];
    }
  }
  for(int k=1;k<=n;k++)
  {
    for(int i=1;i<=n;i++)
    {
      for(int j=1;j<=n;j++)
      {
        map[k][i][j]=map[k-1][i][j];
        if(map[k][i][j]>map[k-1][i][k]+map[k-1][k][j]+cost[k])
        {
          map[k][i][j]=map[k-1][i][k]+map[k-1][k][j]+cost[k];
          pre[i][j]=pre[i][k];
        }
        else  
        if(map[k][i][j]==map[k-1][i][k]+map[k-1][k][j]+cost[k])
        {
          if(pre[i][k]<pre[i][j])
          {
            pre[i][j]=pre[i][k];
          }
        }
      }
    }
  }
}

int main()
{
  while(scanf("%d",&n)!=EOF&&n)
  {
    for(int i=1;i<=n;i++)
    {
      for(int j=1;j<=n;j++)
      {
        scanf("%d",&g[i][j]);
        pre[i][j]=j;
      }
    }
    for(int i=1;i<=n;i++)
    {
      scanf("%d",&cost[i]);
    }
    int u,v,tmp;
    while(scanf("%d%d",&u,&v)&&u!=-1&&v!=-1)
    {
      floyd();
      tmp=u;

      printf("From %d to %d :\n",u,v);

      printf("Path: %d",u);

      while(tmp!=v)

      {

          printf("-->%d",pre[tmp][v]);

          tmp=pre[tmp][v];

      }

      printf("\n");

      printf("Total cost : %d\n",map[n][u][v]);

      printf("\n");

    }
  }
  return 0;
}