The Problem — Shortest Path Again?
I used Dijkstra's single source shortest path algorithm but it's giving wrong answer for a few nodes on every test case. Is Dijkstra optimal for this question? If not, why?
Code
void solve()
{
cout << setprecision(12);
int n, m;
cin >> n >> m;
vpll cost(n, {INFF, INFF}); //cost will save minimum cost to reach ith node from node 0. cost[i].first is the
//cost and cost[i].second is the number of edges used till now (basically k).
cost[0] = {0, 0}; // cost to reach 0th node is 0 and 0 edges used till now.
vector<vpll> graph(n); // graph saves cost-of-edge (w) and the connected vertex.
rep(i, 0, m)
{
int x, y, w;
cin >> x >> y >> w;
x--;
y--;
graph[x].pb({w, y});
graph[y].pb({w, x});
}
vb visited(n);
int count = 0;
while (count < n)
{
ll curr = INFF;
int from = 0;
rep(i, 0, n) // selecting the closest node. saved as 'from'.
{
if (cost[i].first < curr && !visited[i])
{
curr = cost[i].first;
from = i;
}
}
rep(i, 0, graph[from].size()) // calculating minimum cost for every node by using edges of current node ('from').
{
if (curr + graph[from][i].first * (cost[from].second + 1) < cost[graph[from][i].second].first)
{
cost[graph[from][i].second].first = curr + graph[from][i].first * (cost[from].second + 1);
cost[graph[from][i].second].second = cost[from].second + 1;
}
}
visited[from] = 1;
count++;
}
rep(i, 0, n)
{
if (cost[i].first == INFF)
{
cout << -1 << "\n";
}
else
cout << cost[i].first << "\n";
}
return;
}