➤ Problem Link : TRAFFICN
👉 Hint : edit please
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
vector<pair<ll,ll> >adj[100001];
vector<pair<ll,ll> >adj2[100001];
ll dis[100001];
ll dis2[100001];
typedef struct node NODE;
ll djikstra2(ll src,ll end,ll n)
{
set<pair<ll,ll> >s;
s.insert(make_pair(0,src));
for(ll i=0;i<=n;i++)
dis2[i]=INT_MAX;
dis2[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=adj2[v].begin();i!=adj2[v].end();i++)
{
ll ind=(*i).first;
ll time=(*i).second;
if(dis2[ind]>dis2[v]+time)
{
if(dis2[ind]!=INT_MAX)
{
s.erase(s.find(make_pair(dis2[ind],ind)));
}
dis2[ind]=dis2[v]+time;
s.insert(make_pair(dis2[v]+time,ind));
}
}
}
if(dis2[end]!=INT_MAX)
return dis2[end];
return -1;
}
ll djikstra(ll src,ll end,ll n)
{
set<pair<ll,ll> >s;
s.insert(make_pair(0,src));
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));
}
}
}
return dis[end];
}
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,k,val;
cin>>n>>m>>k>>a>>b;
for(ll i=0;i<=n;i++)
{
adj[i].clear();
adj2[i].clear();
}
for(ll i=0;i<m;i++)
{
cin>>x>>y>>t;
adj[x].push_back(make_pair(y,t));
adj2[y].push_back(make_pair(x,t));
}
ll ans=djikstra(a,b,n);
ll ans2=djikstra2(b,a,n);
for(int i=0;i<k;i++)
{
cin>>x>>y>>val;
ans=min(ans,min(dis[x]+val+dis2[y],dis[y]+val+dis2[x]));
}
if(ans<INT_MAX)
cout<<ans<<endl;
else
cout<<"-1"<<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.