Powered by:NEFU AB-IN

Link

L2-001 紧急救援 (25 分)

• 题意

  作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

• 思路

  题意：给定一张无向有权图，求出点1到点n的 最短路的数量 和 最短路中点权最大值

  之前我们有做过无权图的最短路算法，那时候我们直接对$spfa$进行操作就好了
  然而这道题，$spfa$就不能直接操作，但是$dijkstra$就可以

  原因在于$dijkstra$中，每个点只被遍历一次，在它被操作前最后一次更新后dis和sum一定是固定的
  但是spfa算法不一样，它并没有所谓“某次更新后就不会改变”的情况，spfa的最短路和最短路数在queue为空之前一直有被更新的可能，一个点可能进入queue多次

  所以dijkstra直接操作即可，而spfa不能直接操作（可以进行dp操作，记录每个点松弛前和松弛后的路径条数）

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2022-04-19 15:23:55
  * @FilePath: \ACM\GPLT\L2-001.CPP
  * @LastEditTime: 2022-04-19 15:52:36
  */
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #define MP make_pair
  #define SZ(X) ((int)(X).size())
  #define IOS                                                                                                            \
      ios::sync_with_stdio(false);                                                                                       \
      cin.tie(0);                                                                                                        \
      cout.tie(0);
  #define DEBUG(X) cout << #X << ": " << X << endl;
  typedef pair<int, int> PII;
  const int INF = 0x3f3f3f3f;
  const int N = 1010;
  
  int st[N], dist[N], ww[N], num[N], people[N], pre[N];
  vector<PII> g[N];
  
  void dij(int s)
  {
      memset(pre, -1, sizeof pre); // 链表记录上一个节点是什么
      memset(dist, 0x3f, sizeof dist);
      dist[s] = 0;
      ww[s] = people[s]; // 题目中的点权
      num[s] = 1; //路径条数
      priority_queue<PII, vector<PII>, greater<PII>> q;
      q.push({0, s});
      while (q.size())
      {
          auto t = q.top();
          q.pop();
          int u = t.second;
          if (st[u])
              continue;
          st[u] = 1;
          for (auto [v, w] : g[u])
          {
              if (dist[v] > dist[u] + w)
              {
                  dist[v] = dist[u] + w;
                  num[v] = num[u];
                  ww[v] = ww[u] + people[v];
                  pre[v] = u;
                  q.push({dist[v], v});
              }
              else if (dist[v] == dist[u] + w) //如果相等了，说明存在另一条最短路
              {
                  num[v] += num[u];
                  if (ww[v] < ww[u] + people[v]) // 需要更新点权的话就更新，顺便更新链表
                  {
                      ww[v] = ww[u] + people[v];
                      pre[v] = u;
                  }
              }
          }
      }
  }
  
  signed main()
  {
      IOS;
      int n, m, s, d;
      cin >> n >> m >> s >> d;
      for (int i = 0; i < n; ++i)
          cin >> people[i];
      for (int i = 1; i <= m; ++i)
      {
          int u, v, w;
          cin >> u >> v >> w;
          g[u].push_back({v, w});
          g[v].push_back({u, w});
      }
      dij(s);
  
      cout << num[d] << " " << ww[d] << '\n';
      vector<int> path;
      while (d != -1)
      {
          path.push_back(d);
          d = pre[d];
      }
      reverse(path.begin(), path.end());
  
      for (int i = 0; i < SZ(path); ++i)
      {
          cout << path[i] << " "[i == SZ(path) - 1];
      }
      return 0;
  }