Bellmon Ford.cpp

/***Bellmon Ford***/

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, pair<int, int> > PII;
#define MAX 1000009

vector<PII> adj[MAX];
int dist[MAX];
int N, E;

void bellmonFord()
{
    for(int i=1; i<=N-1; i++){
        for(int j=0; j<E; j++){
            int u = adj[j][0].second.first;
            int v = adj[j][0].second.second;
            int cost = adj[j][0].first;
            if(dist[u] + cost < dist[v]) dist[v] = dist[u] + cost;
        }
    }
    for(int i=2; i<=N; i++) printf("%d ", dist[i]);
}

int main()
{
    scanf("%d %d", &N, &E);
    dist[1] = 0;
    for(int i=2; i<=N; i++) dist[i] = 1e9;
    for(int i=0; i<E; i++){
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        adj[i].push_back(make_pair(w, make_pair(u, v)));
    }
    bellmonFord();
}