zoj1456[通俗易懂]

zoj1456[通俗易懂]zoj1456

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

题目大意:

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账号...

(0)


相关推荐

  • Modelsim10.4-win64软件下载安装与破解

    Modelsim10.4-win64软件下载安装与破解1.运行modelsim-win64-10.4-se.exe,安装软件;注意可以不用安装keydrivers,安装路径不要有中文(默认安装路径是C:\modeltech64_10.4) 2.安装过程中一直选择yes即可,注意可以不用安装keydrivers,最后是Done(如果不安装keydrivers)或reboot(如果安装keydrivers)询问,选Yes、…

  • 稻城亚丁4天自由行攻略_稻城亚丁3天旅行攻略

    稻城亚丁4天自由行攻略_稻城亚丁3天旅行攻略有人说向往什么,就去追求什么,才能求仁得仁。稻城亚丁,人称“最后的香格里拉”,藏语也称香巴拉,意为“心中的日月”,外人视为世外桃源,是作为川西秘境中最值得我们去探访的圣地。如果向往真爱和自由,那就带上

  • ios-anchorPoint、position理解[通俗易懂]

    ios-anchorPoint、position理解[通俗易懂]anchorPoint(锚点)是layer的一个属性,下面我们来看看其对view的影响,本文主要通过图片方式展现:锚点用单位坐标来描述也就是图层的相对坐标。在苹果文档中说明左下是(0,0),右上是(1,1),经过试验这个是错的,实际上:图层左上角是{0,0},右下角是{1,1},取值范围不限。单位坐标的意思是指以视图长款为单位来计算,坐标系展示如下:默认一个视图的锚

  • Winform 窗体美化(IrisSkin 换肤库)[通俗易懂]

    Winform 窗体美化(IrisSkin 换肤库)[通俗易懂]IrisSkin换肤库IrisSkin是为MicrosoftVisualStudiodotNET开发的最易用的界面增强dotNET(WinForm)组件包。能完全自动的为应用程序添加支持换肤功能。IrisSkin换肤库百度网盘下载提取码:1pb7皮肤编辑器下载打开下载解压后的文件路径:WinFormSkinDemo\WinFormSkin\WinFormSkin\bi…

  • linux查看GCC版本

    linux查看GCC版本gcc-v打印出你使用gcc的版本信息 gcc-otesttest.c就会编译test.c,生成可执行文件test然后./test就会运行test

  • 到现在你还不知道k9s吗,那你是落后了!

    到现在你还不知道k9s吗,那你是落后了!

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号