题目描述
blablabla
样例
using node=tuple<int,int,int>;
typedef pair<int,int> PII;
class Solution {
public:
vector<bool> findAnswer(int n, vector<vector<int>>& edges) {
unordered_map<int,vector<node>> g;
unordered_map<int,vector<PII>> pre;
for(int i=0;i<edges.size();i++){
auto e=edges[i];
int x=e[0],y=e[1],z=e[2];
g[x].emplace_back(y,z,i);
g[y].emplace_back(x,z,i);
}
vector<int> dist(n,1e9);
vector<bool> st(n);
priority_queue<PII,vector<PII>,greater<PII>> q;
q.emplace(0,0);
dist[0]=0;
while(q.size())
{
auto [d,u]=q.top();
q.pop();
if(st[u]) continue;
st[u]=true;
for(auto [v,w,id]:g[u])
{
if(dist[v]==w+d)
{
pre[v].emplace_back(u,id);
}else if(dist[v]>w+d){
pre[v].clear();
pre[v].emplace_back(u,id);
q.emplace(dist[v]=w+d,v);
}
}
}
queue<int> p;
p.push(n-1);
int m=edges.size();
vector<bool> res(m);
vector<bool> vis(n);
while(p.size())
{
auto u=p.front();
p.pop();
if(vis[u]) continue;
vis[u]=true;
for(auto [v,id]:pre[u]){
res[id]=true;
p.push(v);
}
}
return res;
}
};
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla