# Untitled

unknown
plain_text
2 months ago
1.9 kB
2
Indexable
Never
```#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 ";

}```