CSES - Shared codeLink to this code:
https://cses.fi/paste/56b942b47666376d7be871/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fst first
#define snd second
int inf=1e15;
int n,m;
vector<int>dist;
vector<pair<pii,int>>aristas;
vector<vector<pair<int,int>>>adj;
vector<bool>mark;
bool BellmanFord(int source){
dist[source]=0;
for(int i=1;i<n;i++){
bool flag=false;
for(int k=0;k<aristas.size();k++){
int a=aristas[k].fst.fst, b=aristas[k].fst.snd, peso=aristas[k].snd;
if(dist[b]>dist[a]+peso){
flag=true;
dist[b]=dist[a]+peso;
}
}
if(!flag){
break;
}
}
return true;
}
void BFS(int source){
queue<int>cola;
cola.push(source);
set<pii>mark_edges;
while(!cola.empty()){
int nodo=cola.front();
//cout<<nodo<<" ";
cola.pop();
mark[nodo]=true;
for(int i=0;i<adj[nodo].size();i++){
pair<pii,int> edge={{nodo,adj[nodo][i].snd},adj[nodo][i].fst};
if(mark_edges.count(edge.fst)==0){
mark_edges.insert(edge.fst);
aristas.pb(edge);
if(!mark[adj[nodo][i].snd]){
cola.push(adj[nodo][i].snd);
mark[adj[nodo][i].snd]=true;
}
}
}
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
while(t--){
cin>>n>>m;
dist.assign(n+1,inf);
adj.assign(n+1,vector<pair<int,int>>());
mark.assign(n+1,false);
vector<pair<pii,int>>vec, al_fin;
for(int i=1;i<=m;i++){
int x,y,peso;cin>>x>>y>>peso;
vec.pb({{x,y},peso});
//aristas.pb({{x,y},peso});
}
sort(vec.begin(),vec.end());
for(int i=0;i<vec.size();i++){
pair<pii,int>aux=vec[i];
al_fin.pb(aux);
while(i<vec.size() && vec[i].fst==aux.fst){
i++;
}
i--;
}
for(int i=0;i<al_fin.size();i++){
adj[al_fin[i].fst.fst].pb({al_fin[i].snd,al_fin[i].fst.snd});
}
BFS(1);
//cout<<aristas.size()<<"\n";
BellmanFord(1);
for(int i=1;i<=n;i++){
cout<<dist[i]<<" ";
}
cout<<"\n";
}
return 0;
}
/*
5 10
1 2 6
1 4 7
2 4 8
4 5 9
5 1 2
4 3 -3
2 5 -4
5 3 7
2 3 5
3 2 -2
*/