Loading... # ACWing 383 观光 题解 ## 题目描述 “您的个人假期”旅行社组织了一次比荷卢经济联盟的巴士之旅。 比荷卢经济联盟有很多公交线路。 每天公共汽车都会从一座城市开往另一座城市。 沿途汽车可能会在一些城市（零或更多）停靠。 旅行社计划旅途从$S$城市出发，到$F$城市结束。 由于不同旅客的景点偏好不同，所以为了迎合更多旅客，旅行社将为客户提供多种不同线路。 游客可以选择的行进路线有所限制，要么满足所选路线总路程为$S$到$F$的最小路程，要么满足所选路线总路程仅比最小路程多一个单位长度。  如上图所示，如果$S=1，F=5$则这里有两条最短路线 $1→2→5,1→3→5$，长度为$6$；有一条比最短路程多一个单位长度的路线$1→3→4→5$，长度为$7$。 现在给定比荷卢经济联盟的公交路线图以及两个城市$S$和$F$，请你求出旅行社最多可以为旅客提供多少种不同的满足限制条件的线路。 ## 输入 第一行包含整数$T$，表示共有$T$组测试数据。 每组数据第一行包含两个整数$N$和$M$，分别表示总城市数量和道路数量。 接下来$M$行，每行包含三个整数$A,B,L$，表示有一条线路从城市$A$通往城市$B$，长度为$L$。 需注意，线路是**单向的**，存在从$A$到$B$的线路不代表一定存在从$B$到$A$的线路，另外从城市$A$到城市$B$可能存在多个不同的线路。 接下来一行，包含两个整数$S$和$F$，数据保证$S$和$F$不同，并且$S、F$之间至少存在一条线路。 ## 输出 每组数据输出一个结果，每个结果占一行。 数据保证结果不超过$10^9$。 ## 解题思路 本题中， 最终答案的路线数目可以分为两个部分： - 从$S$到$F$的最短路的条数 - 从$S$到$F$的次短路的条数 - 其中， "次短路"必须满足其长度恰好为最短路+1 因此， 不难看出， 这道题需要求出单源最短路和单源次短路， 并在求解过程中更新状态信息， 因此本题的难点在与如何求得单源次短路。 回想堆优化的Dijstra算法， 其算法求解的过程是通过维护从源点$S$到每一个点的最小距离的小根堆， 并且每次贪心的选择距离最短的节点更新其他节点， 从而达到全局最小的贪心算法。 因此， 可以通过维护一个从源点$S$到每一个点的次小距离的小根堆， 从而求得到达全局的最小距离。 - Q:为什么不只维护最短距离，如果当前距离小于最短距离， 则更新次短路条数， 这样不是就不用维护最小距离的小根堆了吗？ - A:如果只维护最短路的信息， 会导致次短路的信息丢失， 可能影响到后续节点的更新， 如下图所示<br><br>在从堆中取出三号节点的时候， 只附带了三号节点的最小值的信息， 因此四号节点丢失了次小值。 - Q:如何维护最小值和次小值堆呢？ - A:可以维护一个优先队列， 在优先队列中同时维护最小值和次小值的信息， 并通过特定的标记将他们区分开 - Q:如何更新最小值和次小值 - A:可以分情况讨论，设当前距离为`d`: 1. 如果`d + w[i] < dist[j][0]`: 1. `dist[j][1] = dist[j][0]` 2. `dist[j][0] = d + w[i]` 3. `dist[j][0], dist[j][1]`进优先队列 2. 如果`d + w[i] == dist[j][0]`: 1. `dist[j][1] = dist[j][0]` 2. `dist[j][1]`进优先队列 3. 如果`d + w[i] < dist[j][1]`: 1. `dist[j][1] = d + w[i]` 2. `dist[j][1]`进优先队列 4. 如果`d + w[i] == dist[j][1]`: 1. `dist[j][1] = dist[j][0]` - Q:如何更新最短路次短路条数 - A:可以在更新距离的时候同时更新, 设`cnt[i][0]`为最短路条数， `cnt[i][1]`为次短路条数, `type`为二值类型， 用于判别最短路还是次短路: 1. 如果`d + w[i] < dist[j][0]`: 1. `cnt[j][1] = cnt[j][0]` 2. `cnt[j][0] = cnt[i][type]` 2. 如果`d + w[i] == dist[j][0]`: 1. `cnt[j][0] += cnt[i][type]` 3. 如果`d + w[i] < dist[j][1]`: 1. `cnt[j][1] = cnt[i][type]` 4. 如果`d + w[i] == dist[j][1]`: 1. `cnt[j][1] += cnt[i][type]` ## AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #include <queue> #define endl '\n' using namespace std; const int N = 2e5 + 10; typedef pair<int, int> PII; typedef struct A { int u; int type; int dist; bool operator>(const A& it) const { return dist > it.dist; } } rec; int t; int n, m; int h[N], e[N], ne[N], w[N], idx; int s, f; int dist[N][2]; int cnt[N][2]; bool st[N][2]; void init() { memset(h, -1, sizeof h); idx = 0; } void add(int a, int b, int c) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++; } void dijstra() { memset(dist, 0x3f, sizeof dist); memset(st, 0, sizeof st); memset(cnt, 0, sizeof cnt); priority_queue<rec, vector<rec>, greater<rec>> heap; heap.push({s, 0, 0}); dist[s][0] = 0; cnt[s][0] = 1; while(heap.size()) { auto t = heap.top(); int u = t.u, type= t.type, d = t.dist; heap.pop(); if(st[u][type]) continue; st[u][type] = true; for(int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if(d + w[i] < dist[j][0]) { dist[j][1] = dist[j][0]; heap.push({j, 1, dist[j][1]}); cnt[j][1] = cnt[j][0]; dist[j][0] = d + w[i]; heap.push({j, 0, dist[j][0]}); cnt[j][0] = cnt[u][type]; } else if(d + w[i] == dist[j][0]) { cnt[j][0] += cnt[u][type]; } else if(d + w[i] < dist[j][1]) { dist[j][1] = d + w[i]; heap.push({j, 1, dist[j][1]}); cnt[j][1] = cnt[u][type]; } else if(d + w[i] == dist[j][1]) { cnt[j][1] += cnt[u][type]; } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin >> t; while(t --) { init(); cin >> n >> m; for(int i = 1; i <= m; i ++) { int a, b, c; cin >> a >> b >> c; add(a, b, c); } cin >> s >> f; dijstra(); int ans = cnt[f][0]; if(dist[f][1] == dist[f][0] + 1) ans += cnt[f][1]; cout << ans << endl; } return 0; } ``` 最后修改：2025 年 03 月 24 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏