PTA 旅游规划(25 分)

7-10 旅游规划(25 分)

有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序,帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的,那么需要输出最便宜的一条路径。

输入格式:

输入说明:输入数据的第1行给出4个正整数N、M、S、D,其中N(2≤N≤500)是城市的个数,顺便假设城市的编号为0~(N−1);M是高速公路的条数;S是出发地的城市编号;D是目的地的城市编号。随后的M行中,每行给出一条高速公路的信息,分别是:城市1、城市2、高速公路长度、收费额,中间用空格分开,数字均为整数且不超过500。输入保证解的存在。

输出格式:

在一行里输出路径的长度和收费总额,数字间以空格分隔,输出结尾不能有多余空格。

输入样例:

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

输出样例:

3 40
#include<bits/stdc++.h>
using namespace std;
#define maxn 0x7fffffff
int mat[505][505],vis[505],pay[505][505];
/*
mat 是图的邻接矩阵表示,vis是标记数组 , pay 是花费的邻接矩阵表示
*/
int dis[505],cost[505],n,m,path[505];  //最短路 + 路径输出
//n 是点的个数 标记为 0 ~ n-1 , 
//dis 最短路记录数组,cost 最小花费记录数组,path 路径记录数组
void dijkstra(int s) //修改后的最短路算法,+path 记录 和 花费计算
{
  int i,j;
  memset(vis,0,sizeof(vis));//清空标记数组
  for(i=0;i<n;i++)
  {
      /*
      用mat临接矩阵的值初始化dis 的值
      用pay临接矩阵的值初始化cost 的值
      */
      dis[i]=mat[s][i]; 
      cost[i]=pay[s][i];
      if(dis[i]!=maxn) //无穷大代表此路不通 path[i] =-1,否则就在路径加入这个点
          path[i]=s;
      else path[i]=-1;
  }
  vis[s]=1;//起始点标记
  dis[s]=0;//自己到自己的花费cost = 0
  cost[s]=0;
  for(i=1;i<n;i++)
  {
      int k=s,u=maxn;
      /*
      找出到s距离最短&没标记的点,作为中转点更新dis值
      */
      for(j=0;j<n;j++)
      {
          if(!vis[j]&&dis[j]<u)
          {
              u=dis[j];
              k=j;
          }
      }
      vis[k]=1;//标记这个点
      for(j=0;j<n;j++)
      {
          if(!vis[j]&&mat[k][j]!=maxn)
          {
              /*
              用这个点更新dis值,cost 和 dis同步更新,参数值相同
              如果把k作为中转点成功缩减了dis值,就让k点加入path路径里
              */
              if(dis[j]>dis[k]+mat[k][j])
              {
                  dis[j]=dis[k]+mat[k][j];
                  cost[j]=cost[k]+pay[k][j];
                  path[j]=k;
              }
              /*
              最短路径dis相同的话,选择花费最少的,最小cost
              */
              else if(dis[j]==dis[k]+mat[k][j])
              {
                  /*
                  如果这个花费更加优,那么把这个点加入,更新最优秀的路径
                  最后path里面记录的是最优路径
                  */
                  if(cost[j]>cost[k]+pay[k][j])
                  {
                      cost[j]=cost[k]+pay[k][j];
                      path[j]=k;
                  }
              }
          }
      }
  }
}
void print(int s,int t)
{
    stack<int>q;
    /*
    从path里溯源t = path[t],返回上一个和t联通的路径,由后往前,把s~t路径放入队列里面,然后输出
    */
    while(t!=s)
    {
        q.push(t);
        t=path[t];
    }
    q.push(t);
    while(!q.empty())
    {
        cout<<q.top()<<" ";
        q.pop();
    }
}
int main()
{
    int s,t,a,b,d,w,i,j;
    cin>>n>>m>>s>>t;
    for(i=0;i<n;i++)
       for(j=0;j<n;j++)
          mat[i][j]=pay[i][j]=maxn;
    /*
    初始化数组,让距离邻接矩阵数组值 = 无穷大,花费邻接矩阵的值 = 无穷大
    这个计算方式对无向图和有向图同样适用,只需要部分修改
    */
    for(i=0;i<m;i++)
    {
        cin>>a>>b>>d>>w;
        if(mat[a][b]>d)
        {
            mat[a][b]=mat[b][a]=d;
            pay[a][b]=pay[b][a]=w;
        }
        else if(mat[a][b]==d)
        {
            if(pay[a][b]>w)
               pay[a][b]=pay[b][a]=w;
        } // 输入进行处理,最短路
    }
    dijkstra(s); // 寻找从 s 开始 单源最短路
   // print(s,t);// 输出路径, S 到 T 的路径
    cout<<dis[t]<<" "<<cost[t]<<endl;  // dist 指的是 距离 dis[t] 指的是花费
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏云时之间

算法导论系列:分治算法

说起分治法,大家一定也都听过秦始皇采用郡县制将国家分为三十六郡的故事,我们常说”山高皇帝远”,意思就是山高路远,皇帝都管不了,实际上无论皇帝多远,山有多高,整个...

702
来自专栏数据结构与算法

P1288 取数游戏II

题目描述 有一个取数的游戏。初始时,给出一个环,环上的每条边上都有一个非负整数。这些整数中至少有一个0。然后,将一枚硬币放在环上的一个节点上。两个玩家就是以这个...

3458
来自专栏数据结构与算法

n皇后问题

1295 N皇后问题  时间限制: 2 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果 题目描述 Descripti...

2636
来自专栏aCloudDeveloper

算法导论第二章小试牛刀

Author: bakari   Date: 2015.9.11 《算法导论》真是一本让人又爱又恨的书,爱自然是因为它精简凝练的算法呈现,读来让人欲罢不能;至于...

2269
来自专栏ml

HDUOJ-----Be the Winner

1 此题用到的概念: 【定义1】:若一堆中仅有一个石子,则被称为孤单堆。若大于1个,则称为充裕堆。 【定义2】:T态中,若充裕堆的堆数大于等于2,则称为完全利他...

2558
来自专栏落影的专栏

程序员进阶之算法练习(三十一)

BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。

1253
来自专栏企鹅号快讯

黑客们都是如何给勒索软件加密的?

加密是计算机科学中历史最长久的一种计算了。早在二战时期,德国就制造了Enigma密码机,来传输机密信息。计算机科学的祖师爷之一图灵也参与了对Enigma密码的破...

1839
来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第四章 寻路(AStar/A星/A*)算法 (上)

一提到“A*算法”,可能很多人都有"如雷贯耳"的感觉。用最白话的语言来讲:把游戏中的某个角色放在一个网格环境中,并给定一个目标点和一些障碍物,如何让角色快速“绕...

1846
来自专栏落影的专栏

程序员进阶之算法练习(二十三)

前言 趁着8月还没结束,更新一篇算法练习。 正文 1. Alyona and mex 题目链接 题目大意: mex()定义:mex(arr)是 数组arr的...

3897
来自专栏趣谈编程

冒泡排序

面试官: 写一个冒泡排序吧 冒泡排序是一个比较经典和简单的排序算法,今天我们从从算法本身,时间复杂度以及稳定性方面来看看冒泡排序,这些方面也是研究其他排序算法的...

1749

扫码关注云+社区