➤ Problem Link : HIGHWAYS
👉 Hint : Find shortest path in graph (Djikstra)
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
vector<pair<ll,ll> >adj[100001];
ll djikstra(ll src,ll end,ll n)
{
set<pair<ll,ll> >s;
s.insert(make_pair(0,src));
ll dis[n+1];
for(ll i=0;i<=n;i++)
dis[i]=INT_MAX;
dis[src]=0;
while(!s.empty())
{
pair<ll,ll>p=*(s.begin());
s.erase(s.begin());
ll v=p.second;
vector<pair<ll,ll> > :: iterator i;
for(i=adj[v].begin();i!=adj[v].end();i++)
{
ll ind=(*i).first;
ll time=(*i).second;
if(dis[ind]>dis[v]+time)
{
if(dis[ind]!=INT_MAX)
{
s.erase(s.find(make_pair(dis[ind],ind)));
}
dis[ind]=dis[v]+time;
s.insert(make_pair(dis[v]+time,ind));
}
}
}
if(dis[end]!=INT_MAX)
return dis[end];
return -1;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
ll n,m,a,b,x,y,t;
cin>>n>>m>>a>>b;
for(ll i=0;i<=n;i++)
adj[i].clear();
for(ll i=0;i<m;i++)
{
cin>>x>>y>>t;
adj[x].push_back(make_pair(y,t));
adj[y].push_back(make_pair(x,t));
}
ll ans=djikstra(a,b,n);
if(ans==-1)
cout<<"NONE"<<endl;
else
cout<<ans<<endl;
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.