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;
}
Essentially, this doesn't work because Dijkstra's algorithm finds the shortest path in terms of sum of edge weights, but does not care about the number of edges used (which is important in this problem). Here's a counterexample:
Shortest path to node 3 is the path 1 -> 2 -> 3, giving the value 1*2 + 2*1 = 4. Dijkstra's algorithm would give this as well. However, to node 4, the algorithm would give the path 1 -> 2 -> 3 -> 4, giving a value of 1*2 + 2*1 + 3*2 = 10, which isn't optimal. Optimal path is 1 -> 3 -> 4, which gives the value 1*5 + 2*2 = 9.