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.

2 Likes

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

//