Looking at question,Its dijstra implementation↵
↵
#include<bits/stdc++.h>↵
#include <iterator>↵
#include <iostream>↵
#include <numeric>↵
#include <math.h>↵
#define ll long long↵
#define ull long↵
#define mpa make_pair↵
#define pb push_back↵
#define ff first↵
#define pii pair<ll,ll>↵
#define dd long long↵
#define trace(x) cerr << #x << " : " << x << endl↵
#define ss second↵
#define boost ios_base::sync_with_stdio(0)↵
#define forp(i,a,b) for(ll i=a;i<=b;i++)↵
#define rep(i,n) for(ll i=0;i<n;++i)↵
#define ren(i,n) for(ll i=n-1;i>=0;i--)↵
#define forn(i,a,b) for(ll i=a;i>=b;i--)↵
#define all(c) (c).begin(),(c).end()↵
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end();↵
#define sc(x) scanf("%lld",&x)↵
#define clr(x,val) memset(x,val,sizeof(x))↵
#define pr(x) printf("%lld\n",x) ↵
#define gc getchar↵
#define pdd pair<dd,dd>↵
#define prec(x) cout<<fixed<<setprecision(x)↵
#define fre freopen("input.txt","r",stdin),freopen("output.txt","w",stdout)↵
#define ar array ↵
using namespace std;↵
↵
vector<pii> adj[200005];↵
ll mod=1e9+7;↵
ar<ll,5> d[200005]; ↵
ll vis[200005];↵
int main(){↵
↵
ll n,m;↵
cin>>n>>m;↵
while(m--){↵
ll x,y,w;↵
cin>>x>>y>>w;↵
adj[x].pb(mpa(y,w));↵
}↵
↵
for(ll i=1;i<=n;i++){↵
↵
d[i][0]=i;//dest↵
d[i][1]=(i==1?0:1e18);//distance↵
d[i][2]=(i==1?1:0);//no of routes↵
d[i][3]=(i==1?1:1e18);//min_nodes↵
d[i][4]=(i==1?1:0);//max_nodes↵
↵
}↵
↵
↵
↵
↵
↵
↵
set< ar<ll,5> > q;↵
↵
q.insert(d[1]);↵
↵
while(q.size()){↵
ar<ll,5> h=*q.begin();↵
q.erase(q.begin());↵
↵
↵
ll v=h[0];↵
vis[v]=1;↵
↵
for(const auto &u:adj[v]){↵
ll prop=d[v][1]+u.ss;↵
ll to=u.ff;↵
↵
if(d[to][1] > prop){↵
if(q.find(d[to])!=q.end())q.erase(q.find(d[to]));↵
d[to][1]=prop;↵
d[to][2]=d[v][2];↵
d[to][3]=d[v][3]+1;↵
d[to][4]=d[v][4]+1;↵
q.insert(d[to]);↵
}else if(d[to][1]==prop){↵
q.erase(q.find(d[to]));↵
d[to][2]=(d[to][2]+d[v][2])%mod;↵
d[to][3]=max(d[to][3],d[v][3]+1);↵
d[to][4]=min(d[to][4],d[v][4]+1);↵
q.insert(d[to]);↵
}↵
↵
↵
}↵
↵
↵
}↵
↵
cout<<d[n][1]<<" "<<d[n][2]%mod<<" "<<d[n][4]-1<<" "<<d[n][3]-1;↵
↵
↵
}↵
↵
↵
Above is giving Wrong answer for 2 cases can anyone help me to find whats wrong in this
↵
#include <iterator>↵
#include <iostream>↵
#include <numeric>↵
#include <math.h>↵
#define ll long long↵
#define ull long↵
#define mpa make_pair↵
#define pb push_back↵
#define ff first↵
#define pii pair<ll,ll>↵
#define dd long long↵
#define trace(x) cerr << #x << " : " << x << endl↵
#define ss second↵
#define boost ios_base::sync_with_stdio(0)↵
#define forp(i,a,b) for(ll i=a;i<=b;i++)↵
#define rep(i,n) for(ll i=0;i<n;++i)↵
#define ren(i,n) for(ll i=n-1;i>=0;i--)↵
#define forn(i,a,b) for(ll i=a;i>=b;i--)↵
#define all(c) (c).begin(),(c).end()↵
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end();↵
#define sc(x) scanf("%lld",&x)↵
#define clr(x,val) memset(x,val,sizeof(x))↵
#define pr(x) printf("%lld\n",x) ↵
#define gc getchar↵
#define pdd pair<dd,dd>↵
#define prec(x) cout<<fixed<<setprecision(x)↵
#define fre freopen("input.txt","r",stdin),freopen("output.txt","w",stdout)↵
#define ar array ↵
↵
vector<pii> adj[200005];↵
ll mod=1e9+7;↵
ar<ll,5> d[200005]; ↵
ll vis[200005];↵
int main(){↵
↵
ll n,m;↵
cin>>n>>m;↵
while(m--){↵
ll x,y,w;↵
cin>>x>>y>>w;↵
adj[x].pb(mpa(y,w));↵
}↵
↵
for(ll i=1;i<=n;i++){↵
↵
d[i][0]=i;//dest↵
d[i][1]=(i==1?0:1e18);//distance↵
d[i][2]=(i==1?1:0);//no of routes↵
d[i][3]=(i==1?1:1e18);//min_nodes↵
d[i][4]=(i==1?1:0);//max_nodes↵
↵
}↵
↵
↵
↵
↵
↵
↵
set< ar<ll,5> > q;↵
↵
q.insert(d[1]);↵
↵
while(q.size()){↵
ar<ll,5> h=*q.begin();↵
q.erase(q.begin());↵
↵
↵
ll v=h[0];↵
vis[v]=1;↵
↵
for(const auto &u:adj[v]){↵
ll prop=d[v][1]+u.ss;↵
ll to=u.ff;↵
↵
if(d[to][1] > prop){↵
if(q.find(d[to])!=q.end())q.erase(q.find(d[to]));↵
d[to][1]=prop;↵
d[to][2]=d[v][2];↵
d[to][3]=d[v][3]+1;↵
d[to][4]=d[v][4]+1;↵
q.insert(d[to]);↵
}else if(d[to][1]==prop){↵
q.erase(q.find(d[to]));↵
d[to][2]=(d[to][2]+d[v][2])%mod;↵
d[to][3]=max(d[to][3],d[v][3]+1);↵
d[to][4]=min(d[to][4],d[v][4]+1);↵
q.insert(d[to]);↵
}↵
↵
↵
}↵
↵
↵
}↵
↵
cout<<d[n][1]<<" "<<d[n][2]%mod<<" "<<d[n][4]-1<<" "<<d[n][3]-1;↵
↵
↵
}↵
↵
↵
Above is giving Wrong answer for 2 cases can anyone help me to find whats wrong in this
