How can spoj problem HIGHWAY be solved using mst?

HIGHWAY, I have solved this problem using dikstra’s algo, but this probelem has MST tag, no idea how mst can be used in this problem, any help?

1 Like

This problem is purely based on Dijikstra algorithm. I really don’t know why this problem has been tagged as MST. Since question is asking about minimum time from source to destination so MST can’t be used here.


Someone commented he solved it using MST just curious, I guess prim’s algo can be used… :expressionless: