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)


相关推荐

  • 开放API接口_软件接口开放

    开放API接口_软件接口开放前言在开发测试阶段,或者是在写Demo的时候,难免会用到一些测试数据,有时苦于没有可用的接口,需要自己动手去写,但是这样大大降低了效率,前期我也找了一些开放的接口,这篇文章整理一下,以下接口完全免费,不用注册,返回格式全是JSON,所有接口均可无限制使用,有需要的小伙伴可以进来看看。(ps:所有数据来源于网络,如有侵权,请作者联系删除)图片类接口美女图片:https://w…

  • [转载]interp1「建议收藏」

    [转载]interp1「建议收藏」MATLAB中的插值函数为interp1,其调用格式为:yi=interp1(x,y,xi,’method’)其中x,y为插值点,yi为在被插值点xi处的插值结果;x,y为向量,’method’表示采用的插值方法,MATLAB提供的插值方法有几种:’method’是最邻近插值,’linear’线性插值;’spline’三次样条插值;’cub…

  • Activiti最全入门教程「建议收藏」

    Activiti最全入门教程「建议收藏」1:工作流的概念 说明:1)假设:这两张图就是华谊兄弟的请假流程图 2)图的组成部分: A.人物:范冰冰冯小刚王中军 B.事件(动作):请假、批准、不批准  工作流(Workflow),就是“业务过程的部分或整体在计算机应用环境下的自动化”,它主要解决的是“使在多个参与者之间按照某种预定义的规则传递文档、信息或任务的过程自动进行,从

  • php中fread用法,php fread函数与fread函数用法_PHP教程

    php中fread用法,php fread函数与fread函数用法_PHP教程phpfread函数与fread函数用法php教程fread函数与fread函数用法/*fread语法:stringfread(resource$handle,int$length)fread()读取到的字节长度由处理引用的文件指针。读尽快停止对符合下列条件之一:已经读取的字节长度!eof(文件结束)达到一包可用网络(流)已阅读8192字节(打开后用户空间流)*///fread…

  • SQL Server 2008 评估期已过解决方法

    SQLServer2008有180天的试用期,过期后会提示“评估期已过”的提示。1、进入SQLServer安装中心:2、选择“维护”-“版本升级”3、输入密钥:其他的根据提示操作。附S

    2021年12月23日
  • visual studio code注释快捷键怎么用?「建议收藏」

    visual studio code注释快捷键怎么用?「建议收藏」1、单行注释:光标放在第一行任意位置,ctrl+/,取消同理。2、多行注释:光标选中想要注释的所有代码,ctrl+/,取消同理。

发表回复

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

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