Untitled
unknown
plain_text
a year ago
1.9 kB
6
Indexable
#include<bits/stdc++.h> using namespace std; #define f first #define s second // #define mod 1e9+7 #define mp make_pair #define int long long using ii=pair<int,int>; int mod = 1e9+7; int n,m; int mpr=0; vector<vector<ii>> g; vector<int> vis,dis,cnt,mnd,mxd; void dijkstra(){ priority_queue<ii> p; p.push(mp(-0,1)); int curp=-0;//current price int curn=1; // current node cnt[1]=1; while(!p.empty()){ ii curs=p.top(); p.pop(); if(vis[curs.s]==1)continue; vis[curs.s]=1; //need to keep vis here curn=curs.s; curp=-curs.f; for(auto v : g[curs.s]){ if(dis[v.f]>curp+v.s){ dis[v.f]=curp+v.s; p.push(mp(-dis[v.f],v.f)); cnt[v.f]=cnt[curs.s]; // cout<<cnt[v.f]<<" "<<v.f<<"\n"; mnd[v.f]=mnd[curs.s]+1; mxd[v.f]=mxd[curs.s]+1; } /* As cost starts with 1, each edge will be considered*/ /* cnt will count same price edgess at each node*/ else if(dis[v.f]==curp+v.s){ (cnt[v.f]+=cnt[curs.s])%=mod; // cout<<cnt[v.f]<<" "<<v.f<<"\n"; mnd[v.f] = min({mnd[v.f],mnd[curs.s]+1}); mxd[v.f] = max({mxd[v.f],mxd[curs.s]+1}); } } } } signed main(){ cin>>n>>m; g.resize(n+1); vis.assign(n+1,0); cnt.assign(n+1,0); mnd.assign(n+1,0); mxd.assign(n+1,0); dis.assign(n+1,1e15+10); for(int i=0;i<m;i++){ int a,b,c; cin>>a>>b>>c; g[a].push_back(mp(b,c)); } dijkstra(); // cout<<dis[n]<<" "; if(dis[n]!=1e15+10){ cout<<dis[n]<<" "<<cnt[n]<<" "<<mnd[n]<<" "<<mxd[n]<<" "; } else cout<<"-1 "; }
Editor is loading...
Leave a Comment