Я дал граф с V вершинами, E ребрами, исходной вершиной s и числом m
Вес каждого ребра равен one
Я должен найти кратчайший путь ко всем тем узлам, чье расстояние от исходного узла меньше заданного числа m
Мой подход: - Я использовал алгоритм Дейкстры и нашел путь для всех узлов
а затем выбрал те узлы, расстояние которых меньше m, но я получаю время
превышение лимита.
Есть ли какой-нибудь лучший подход или какой-либо алгоритм, который кто-нибудь может предложить?
Обновление: -
Я использовал BFS, но все же получаю TLE в некоторых случаях, я стараюсь не пересекать все узлы, а не только те, чье расстояние меньше m от источника s, и сохраняю их в temp
Пожалуйста, поправьте меня, если мой подход неверен.
Вот мой код
#include <bits/stdc++.h>
using namespace std;
const long long N = 5*1e4;
const long long W = 1e9;
const long long INF = 1e9;
vector<long long> g[N]; //graph
long long dist[N]; //distance
bool visited[N]; // is node visited or not
void shortest_path(long long s,long long m){
fill(dist, dist + N, INF);
fill(visited, visited + N, 0);
dist[s] = 0;
vector<int>temp;
queue<long long>q; //Queue
q.push(s);
while(!q.empty())
{
long long v = q.front();
q.pop();
if(visited[v]) continue;
visited[v] = 1;
temp.push_back(v); //storing nodes in temp
for(auto it: g[v])
{
long long u = it;
if(dist[v] + 1<= m) // nodes those distance is less than m
{
dist[u] = dist[v] + 1;
q.push(u);
}
}
}
for(int i=0;i<temp.size();i++){
cout<<temp[i]<<" ";
}
}
int main()
{
long long n;
cin>>n;
for(long long i = 0; i < n; ++i) g[i].clear();
for(long long i = 0; i < n-1; i++)
{
long long u,v;
cin>>u>>v;
u--;v--;
g[u].push_back(v);
g[v].push_back(u);
}
long long q;
cin>>q;
for(long long i=0;i<q;i++){
long long s,m;
cin>>s>>m;
s--;
shortest_path(s,m);
cout<<endl;
}
return 0;
}