[PAT解题报告] Emergency

题目给了一个图,代表若干个城市,每个城市里有若干人,城市靠道路相连——总体来说是一个无向图,每个节点有一个权值,边也有权值,代表路径长度。然后给定一个起点,是你所在的城市,再给定一个终点——表示目的城市,一旦遇到紧急情况,你需要以最快的速度把尽可能多的人放到目的城市。求两个值 (1) 从起点到终点有多少条最短路径 (2) 走最短路的前提下,你最多能运送多少人到终点?

分析: 这是一个典型的最短路问题。后面还会看到其实PAT最短路的问题还挺多的,但都不是直接求最短路那么简单。比如本题,还要求最短路的长度。我们考虑一下Dijkstra算法的核心步骤:
if (d[i] > d[j] + w(j, i)) then d[i] = d[j] + w(j, i)
其中j是我们目前还没有用过的距离最小的点, w(j, i)表示j到i的距离,我们会用d[j] + w(j, i)更新d[i]的最小距离。
如何计算最短路的条数呢? 玄机也在这里!我们用数组way[x]表示从起点到x的最短路条数。
如果d[i] == d[j] + w(j, i) 原来达到j的最短路加上边(j,i)也是达到j的最短路,于是累加way[i] += way[j]。
如果d[i] > d[j] + w(j, i) 我们更新d[i] = d[j] + w(j, i)的同时,得到了更从起点到j更短的路,所以之前的计算的条数没有意义了,直接有way[i] = way[j]
那么怎样计算最多运送的人数呢?
也是类似的。我们用num[x]表示从起点到达x走最短路能运送的最多的人数。并且b[x]表示在x处有多少人。
如果d[i] == d[j] + w(j, i),  num[i] = max(num[i], num[j] + b[i]) 这是因为我们选择是否从j走到i要看经过j是不是比我们现在带的人多。
如果d[i] > d[j] + w(j, i), 更新d[i] = d[j] + w(j, i)的同时,我们只能用num[i] = num[j] + b[i],因为我们一定要优先走最短路——带的人数是第二关键字,所以我们别无选择,只能选择经过j。
因此,本题关键在于理解dijkstra算法更新的过程,以及最短路的形成——其实本质就是s到i的最短路,包含了s到j的最短路,加上j到i的那条边的长度——一切更新都源于此。

注意: 我假设了两个点间的最短边只有一条,如果有平行边(两点间最短的边有多个),要记录一下最短边的条数,更新的时候
 way[i] = way[k] * edge_count[i, k]
或者way[i] += way[k] * edge_count[i, k]
edge_couint [i, k] 表示i,k之间有多少条边都是最短长度的…… 邻接矩阵要多存一个值。

代码:
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

const int inf = 1000000000;
const int N = 502;

int n;
bool mark[N];
int a[N][N];
int num[N];
int b[N];
int cost[N];
int way[N];

void dijkstra(int s) {
  for (int i = 0; i < n; ++i) {
    cost[i] = inf;
    mark[i] = false;
    num[i] = way[i] = 0;
  }
  num[s] = b[s];
  way[s] = 1;
  cost[s] =  0;
  for (int j = 0; j < n; ++j) {
    int k = -1;
    for (int i = 0; i < n; ++i) {
      if ((!mark[i]) && ((k < 0) || (cost[i] < cost[k]))) {
        k = i;
      }
    }
    mark[k] = true;
    for (int i = 0; i < n; ++i) {
      if ((!mark[i]) && (a[k][i] < inf)) {
        int temp = cost[k] + a[k][i];
        if (temp < cost[i]) {
          cost[i] = temp;
          num[i] = num[k] + b[i];
          way[i] = way[k];
        }
        else if (temp == cost[i]) {
          num[i] = max(num[k] + b[i], num[i]);
          way[i] += way[k];
        }
      }
    }
  }
}


int main() {
int m,from,to;
  scanf("%d%d%d%d",&n,&m,&from,&to);
  for (int i = 0; i < n; ++i) {
    scanf("%d",b + i);
    for (int j = 0; j < n; ++j) {
      a[i][j] = inf;
    }
  }
  for (;m;--m) {
    int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    a[x][y] = a[y][x] = min(a[x][y],z);
  }
  dijkstra(from);
  printf("%d %d\n",way[to], num[to]);
  return 0;
}


原题链接: http://www.patest.cn/contests/pat-a-practise/1003
全部评论
错了,虽然提交了accepted。试试这组数据 6 10 0 2 1 1 1 2 2 3 0 1 1 1 3 2 0 3 1 0 4 2 0 5 3 0 2 4 3 2 3 2 5 1 4 2 2 3 4 1
点赞 回复 分享
发布于 2020-02-01 14:55

相关推荐

认真搞学习:这么良心的老板真少见
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务