题目大意：输入是节点数量，节点序号从到；条边用数组表达，，意味着节点和节点的权重等于。需要考虑从节点为起点，节点为终点的所有最短路。输出是一个数组，为意味着至少在一条最短路上，反之为。

最暴力最直接的解法是直接搜索，那先来分析一个dfs的时间复杂度。因为dfs一般图的时间复杂度难以评估（比如在最好情况下图会退化成链，只需要；在最坏情况下是一个完全图，dfs就等价于数字到的全排列，约等于），所以我想评估一下最坏情况，数据范围是，，也就是说边至多只有条，至多可以为个节点构造完全图。这样计算次数约等于。这显然是远大于次运算的。

然后考虑在dfs上是否有某种剪枝可以使得时间复杂度可以接受。比如说当前遍历的权重和已经超过了之前记录的最短路就剪枝。但是这似乎和遍历顺序有关，如果最短路在最后才被遍历到，那么这个剪枝策略似乎就是无效的。那我就希望最先遍历最短路，如果用贪心的策略来决定dfs的顺序，每次都先选择当前节点能到达的最近的点，似乎只能得到局部最优，而非全局最优。所以我暂时放弃了dfs这个思路。

因为太久没有做最短路的题了，所以我google了一下最短路都有哪些算法，比较好运的是看完dijkstra之后，我感觉它有点可行。dijstra的思路是对于一个固定的起点维护一个到所有节点的距离数组，然后每次遍历这个数组找出离起点最近距离的节点，去更新其它所有节点到起点的距离。时间复杂度是,外层循环是遍历距离数组找出最小距离节点，内层循环是更新起点到其它所有节点的距离（内层循环其实也可以通过遍历边来更新这样总时间复杂度是，但这道题里边和点差不多，所以就不做区分了）。计算次数是。这里感觉时间复杂度能接受，毕竟前面只是个常数，如果数据不是很极端的话，那听起来是可以蒙混过关的。

到目前为止都没啥问题，但是朴素的dijkstra有一个问题，我没有办法记录所有最短路，我只能得到最短路的距离。如果这个问题没法解决，我就只能放弃dijstra这个思路了。但这很容易想到在更新距离数据的时候我可以为每一个节点记录一个前置节点数组，之后可以从后往前回溯回来就能找到这条最短路了！这一步没有额外的时间复杂的开销，但有额外的空间开销。但是我没找到空间复杂度有啥限制（虽然我觉得必然是有限制的），所以暂时忽略先，实在不行就MLE了再说。这里我不太自信，搜了一下，确实有类似的处理。

既然我们已经有了每个节点的前置节点限制，那就通过dfs回溯回来就好了，标记下遍历过的节点不再遍历，时间复杂度就大约是。那总的时间复杂度就是，那这题我觉得思路到目前就已经完全明了了。

于是自信满满提交了一发TLE。但是但是！dijstra有众所周知的优化方法，就是用堆来维护距离数组，这样会被降为，这样应该就稳了，然后交了一发果然AC了。

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
61
62
63
64
65
class Solution {
public:
    int INF = 1e9;

    vector<bool> findAnswer(int n, vector<vector<int>>& edges) {
        int start = 0, end = n - 1;
        vector<vector<int>> pre(n);
        vector<int> d(n, INF);
        vector<bool> visited(n, false);
        vector<vector<pair<int, int>>> G(n);
        for (const auto& e : edges) {
            int u = e[0], v = e[1], w = e[2];
            G[u].push_back({v, w});
            G[v].push_back({u, w});
        }
        using pii = pair<int, int>;
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        d[start] = 0;
        pq.push({0, start});

        while (!pq.empty()) {
            auto [du, u] = pq.top(); pq.pop();
            if (visited[u]) continue;
            visited[u] = true;

            for (auto [v, w] : G[u]) {
                if (!visited[v]) {
                    if (d[u] + w < d[v]) {
                        d[v] = d[u] + w;
                        pre[v].clear();
                        pre[v].push_back(u);
                        pq.push({d[v], v});
                    } else if (d[u] + w == d[v]) {
                        pre[v].push_back(u);
                    }
                }
            }
        }

        set<pair<int, int>> path_edges;
        vector<bool> visited_dfs(n, false);
        dfs(end, start, pre, path_edges, visited_dfs);

        vector<bool> answer(edges.size(), false);
        for (int i = 0; i < edges.size(); ++i) {
            int u = edges[i][0], v = edges[i][1];
            if (path_edges.count({min(u, v), max(u, v)})) {
                answer[i] = true;
            }
        }

        return answer;
    }

    void dfs(int u, int target, const vector<vector<int>>& pre, set<pair<int, int>>& path_edges, vector<bool>& visited_dfs) {
        if (u == target) return;
        if (visited_dfs[u]) return;
        visited_dfs[u] = true;

        for (int v : pre[u]) {
            path_edges.insert({min(u, v), max(u, v)});
            dfs(v, target, pre, path_edges, visited_dfs);
        }
    }
};

实现的时候磕磕绊绊的，gpt老师应该和我平分contribution，最后优先队列的改写，我实在是不记得语法了:(
语法还是需要多加练习。