大家好,又见面了,我是你们的朋友全栈君。
题目大意:
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;
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/159312.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...