[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

相关推荐

10-30 21:47
已编辑
广东财经大学 web前端
小红书 实习 9-10k
哇咔咔嘞:先签小厂,然后去实习,春招找到好的再违约
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务