https://leetcode.cn/problems/find-edges-in-shortest-paths/

思路

从0点到各个点的距离，
然后dfs扩展就行了，只要链接上这个边，仍能等于最小的距离，就说明结果是最小路径上的边。

class Solution {
public:vector<bool> findAnswer(int n, vector<vector<int>>& edges) {vector<vector<tuple<int,int, int>>> maps(n);for(int i=0;i<edges.size();i++){auto it = edges[i];maps[it[0]].emplace_back(it[1], it[2], i);maps[it[1]].emplace_back(it[0], it[2], i);}// 使用dj+堆优化进行搜索全部的结果priority_queue<pair<long long, int> ,vector<pair<long long, int>>, greater<pair<long long,int>> > que;vector<int> vis(n , 0);vector<long long> dis(n, INT_MAX);dis[0] = 0;que.emplace(0, 0);// 0距离0点while(que.size()){auto it = que.top();que.pop();int min_pos = it.second;if(vis[min_pos]) continue;vis[min_pos] = 1;for(auto &[y, w, _]: maps[min_pos]){if(!vis[y] and dis[y]>dis[min_pos]+w){dis[y]=dis[min_pos]+w;que.emplace(dis[y], y);}}}vector<bool > ans(edges.size(), false);if(dis[n-1] == INT_MAX) return ans;// 否则就从n-1点进行dfs扩展vis.clear();vis.resize(n, 0);function<void(int )> dfs = [&](int pos){if(pos<0) return;vis[pos] = 1;for(auto& [y,w,p]:maps[pos]){if(dis[y]+w!=dis[pos]) continue;ans[p] = true;if(!vis[y])dfs(y);}};dfs(n-1);return ans;}
};