acwing-383. 观光

发表于 分类于 阅读次数： Waline： 本文字数： 738 阅读时长 ≈ 2 分钟

考点

  • 次短路

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 50, maxm = 1e5 + 50;
int n, m, s, f, tot, head[maxn], ver[maxm], edge[maxm], nxt[maxm];

void add(int u, int v, int w) {
  ver[++tot] = v, edge[tot] = w, nxt[tot] = head[u], head[u] = tot;
}

void dijkstra() {
  // 第一维代表最短路，第二维代表次短路
  int d[maxn][2], cnt[maxn][2];
  memset(d, 0x3f, sizeof(d)), memset(cnt, 0, sizeof(cnt));
  bool vis[maxn][2];
  memset(vis, 0, sizeof(vis));
  // <路径开销，<节点，类型>>
  priority_queue<pair<int, pair<int, int>>> q;
  d[s][0] = 0, cnt[s][0] = 1;
  q.push({0, {s, 0}});
  while (!q.empty()) {
    int dis = q.top().first, u = q.top().second.first,
        type = q.top().second.second;
    q.pop();
    if (vis[u][type]) continue;
    vis[u][type] = 1;
    dis = -dis;
    for (int i = head[u]; ~i; i = nxt[i]) {
      int v = ver[i], w = edge[i];
      if (d[v][0] > dis + w) {
        d[v][1] = d[v][0], cnt[v][1] = cnt[v][0], q.push({-d[v][1], {v, 1}});
        d[v][0] = dis + w, cnt[v][0] = cnt[u][type], q.push({-d[v][0], {v, 0}});
      } else if (d[v][0] == dis + w) {
        cnt[v][0] += cnt[u][type];
      } else if (d[v][1] > dis + w) {
        d[v][1] = dis + w;
        cnt[v][1] = cnt[u][type];
        q.push({-d[v][1], {v, 1}});
      } else if (d[v][1] == dis + w) {
        cnt[v][1] += cnt[u][type];
      }
    }
  }
  cout << (d[f][1] == d[f][0] + 1 ? cnt[f][0] + cnt[f][1] : cnt[f][0]) << endl;
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    memset(head, -1, sizeof(head)), tot = -1;
    cin >> n >> m;
    for (int u, v, w, i = 1; i <= m; ++i) {
      cin >> u >> v >> w;
      add(u, v, w);
    }
    cin >> s >> f;
    dijkstra();
  }
  return 0;
}

思路

次短路的提升题，难点在于要同时记录最短路和次短路的个数。

设第一维代表最短路，第二维代表次短路，

那么d[u][0]和d[u][1]分别代表点u的最短路和次短路长度，

cnt[u][0]和cnt[u][1]分别代表点u的最短路个数和次短路个数。

由于每个点的最短路和次短路的个数不一定相同，

所以还需要在堆中新增一个变量type代表当前点使用的是最短路还是次短路：

1
2
// <路径开销，<节点，类型>>
priority_queue<pair<int, pair<int, int>>> q;

设当前节点u，使用类型type的长度为dis，要扩展到节点v，边权为w，有如下情况：

  1. 如果d[v][0] > dis + w，即最短路会被更新

    那么当前最短路就会变成次短路，当前最短路的个数就会变成次短路的个数：

    1
    d[v][1] = d[v][0], cnt[v][1] = cnt[v][0], q.push({-d[v][1], {v, 1}});

    当前最短路变成dis + w，个数等于cnt[u][type]：

    1
    d[v][0] = dis + w, cnt[v][0] = cnt[u][type], q.push({-d[v][0], {v, 0}});

  2. 如果d[v][0] == dis + w，当前开销等于最短路，直接新增最短路个数

    1
    cnt[v][0] += cnt[u][type];

  3. 如果d[v][1] > dis + w 且 d[v][0] < dis + w，即次短路会被更新

    次短路变成dis + w，个数等于cnt[u][type]:

    1
    d[v][1] = dis + w, cnt[v][1] = cnt[u][type], q.push({-d[v][1], {v, 1}});

  4. 如果d[v][1] == dis + w，当前开销等于次短路，直接新增次短路个数

    1
    cnt[v][1] += cnt[u][type];