题解：观光路线计数（Sightseeing）

题目分析

题目要求计算从起点S到终点F的所有最短路径（长度为d）和次短路径（长度为d+1）的总数。关键在于同时跟踪每个节点的最短和次短距离，并统计对应的路径数量。

算法思路

使用改进的Dijkstra算法，同时维护每个节点的最短距离和次短距离，以及对应的路径数。具体步骤如下：

1. 状态定义：用 ds[i][0] 表示节点i的最短距离，ds[i][1] 表示次短距离；cnt[i][0] 和 cnt[i][1] 分别记录最短和次短路径的数量。
2. 优先队列：按距离从小到大处理节点，确保先处理更短的路径。
3. 状态更新：遍历每个节点的出边，用当前路径长度更新邻接节点的最短或次短距离，并累加路径数。
4. 终止条件：当终点F的最短和次短距离均被确定后，统计符合条件的路径总数（最短路径数 + 次短路径数（若次短距离为d+1））。

代码解析

数据结构与变量

• ds[maxn][2]：存储每个节点的最短（ds[i][0]）和次短距离（ds[i][1]）。
• cnt[maxn][2]：存储每个节点最短（cnt[i][0]）和次短路径（cnt[i][1]）的数量。
• pos[maxn]：记录每个节点被处理的次数（最多处理2次：最短和次短）。
• priority_queue<P, vector<P>, greater<P>> q：优先队列（小根堆），按距离排序，确保每次处理当前最短路径。

核心函数 Dijkstra(int s, int t)

1. 初始化：将起点的最短距离设为0，路径数设为1；其他节点距离初始化为无穷大（0x3f3f3f3f）。
2. 处理队列：每次取出队列中距离最小的节点x，若x已被处理2次（pos[x] > 1），则跳过（因最短和次短距离已确定）。
3. 遍历邻接边：对x的每条出边x→y，计算新的路径长度z = ds[x][当前处理状态] + 边权。
   • 更新最短距离：若z小于y的最短距离，交换z和最短距离，更新路径数，并将新的最短距离入队。
   • 累加最短路径数：若z等于y的最短距离，直接累加路径数。
   • 更新次短距离：若z介于y的最短和次短距离之间，更新次短距离和路径数；若z等于次短距离，累加路径数。
4. 结果计算：终点t的最短路径数加上次短路径数（仅当次短距离为最短距离+1时）。

关键逻辑说明

• 优先队列：确保每次处理的是当前已知最短路径的节点，符合Dijkstra算法的贪心性质。
• 状态限制：pos[x] > 1 跳过处理，避免重复计算（每个节点最多贡献最短和次短路径）。
• 路径计数：通过累加cnt[x][当前状态]到邻接节点的cnt[y][对应状态]，确保路径数正确统计。

复杂度分析

• 时间复杂度：每个节点最多入队2次（最短、次短），每条边被处理2次，总时间复杂度为O(M log N)，其中M是边数，N是节点数。
• 空间复杂度：使用邻接表存储图，空间复杂度为O(M + N)。

示例验证

以题目第一个测试用例为例：
输入为5个城市，8条边，起点1，终点5。

• 最短路径长度为6（如1→2→5和1→3→5），路径数为2。
• 次短路径长度为7（如1→3→4→5），路径数为1。
• 总路径数为2 + 1 = 3，与输出一致。
  ###标程

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> P;
const int maxn = 1005, maxm = 10005;
int T, N, M, S, F, ds[maxn][2], cnt[maxn][2], pos[maxn];
int tot, head[maxn], to[maxm], nxt[maxm], cost[maxm];

inline void add(int x, int y, int z) { to[++tot] = y, cost[tot] = z, nxt[tot] = head[x], head[x] = tot; }

int Dijkstra(int s, int t)
{
    memset(ds, 0x3f, sizeof(ds));
    memset(cnt, 0, sizeof(cnt));
    memset(pos, 0, sizeof(pos));
    priority_queue<P, vector<P>, greater<P> > q;  // 修正：在模板参数中添加空格
    ds[s][0] = 0, cnt[s][0] = 1;
    q.push(P(0, s));
    while (q.size())
    {
        int x = q.top().second;
        q.pop();
        if (pos[x] > 1)
        {
            if (x == t)
                break;
            continue;
        }
        for (int i = head[x]; i; i = nxt[i])
        {
            int y = to[i], z = ds[x][pos[x]] + cost[i], c = cnt[x][pos[x]];
            if (z == ds[y][0])
                cnt[y][0] += c;
            else if (z < ds[y][0])
                swap(z, ds[y][0]), swap(c, cnt[y][0]), q.push(P(ds[y][0], y));
            if (z == ds[y][1])
                cnt[y][1] += c;
            else if (ds[y][0] < z && z < ds[y][1])
                ds[y][1] = z, cnt[y][1] = c, q.push(P(ds[y][1], y));
        }
        ++pos[x];
    }
    return cnt[t][0] + (ds[t][1] == ds[t][0] + 1 ? cnt[t][1] : 0);
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        memset(head, 0, sizeof(head));
        tot = 0;
        scanf("%d%d", &N, &M);
        for (int i = 1, x, y, z; i <= M; ++i)
            scanf("%d%d%d", &x, &y, &z), add(x, y, z);
        scanf("%d%d", &S, &F);
        printf("%d\n", Dijkstra(S, F));
    }
    return 0;
}

总结

该代码通过改进的Dijkstra算法高效地同时跟踪最短和次短距离，并统计路径数，确保在O(M log N)时间内解决问题，适用于题目给定的规模（N≤1000，M≤10000）。