CSES problem Investigation https://cses.fi/problemset/task/1202/

Revision en1, by presscoder, 2020-09-18 22:40:22

Looking at question,Its dijstra implementation

include<bits/stdc++.h>

include

include

include

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 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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English presscoder 2020-09-18 22:41:01 949
en1 English presscoder 2020-09-18 22:40:22 2441 Initial revision (published)