We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
vector shortestReach(int n, vector> edges, int s) {
vector<pair<int,int>>adj[n+1];
for(int i = 0;i<edges.size();i++)
{
int x = edges[i][0];
int y = edges[i][1];
int z = edges[i][2];
adj[x].push_back(make_pair(y,z));
adj[y].push_back(make_pair(x,z));
}
priority_queue< pair<int,int> , vector<pair<int,int>> , greater<pair<int,int>> >pq;
vector<long long int>dist( n+1 , INT_MAX);
bool visited[n+1];
for(int i = 0;i<=n;i++)
{
visited[i] = false;
}
dist[s] = 0;
pq.push(make_pair(0,s));
visited[s] = true;
while(!pq.empty())
{
int u = pq.top().second;
pq.pop();
visited[u] = true;
for (int i =0;i<adj[u].size();i++)
{
// Get vertex label and weight of current adjacent
// of u.
int v = adj[u][i].first;
int weight = adj[u][i].second;
if(!visited[v])
{
// If there is shorted path to v through u.
if (dist[v] > dist[u] + weight)
{
// Updating distance of v
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}
}
vector<int>res;
for(int i = 1;i<=n;i++)
{
if(i==s)
continue;
if(dist[i]==INT_MAX)
{
dist[i] = -1;
}
res.push_back(dist[i]);
}
return res;
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Dijkstra: Shortest Reach 2
You are viewing a single comment's thread. Return to all comments →
vector shortestReach(int n, vector> edges, int s) {
}