Grafs

#include <iostream>
#include <vector>
using namespace std;
const int INF = 1000000000;

int main() {
    int n, m;
    cin >> n >> m;
    vector < vector < pair<int, int> > > g(n);
    int v, r;
    for (int i=0; i < m; i++) {
        cin >> v >> r;
        g[v].push_back(make_pair(v, r));
    }
    int s = 1; // стартовая вершина

    vector<int> d(n, INF), p(n);
    d[s] = 0;
    vector<char> u(n);
    for (int i = 0; i < n; ++i) {
        int v = -1;
        for (int j = 0; j < n; ++j)
            if (!u[j] && (v == -1 || d[j] < d[v]))
                v = j;
        if (d[v] == INF)
            break;
        u[v] = true;

        for (size_t j = 0; j < g[v].size(); ++j) {
            int to = g[v][j].first,
                len = g[v][j].second;
            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                p[to] = v;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        cout << d[i] << " ";
    }
    return 0;
}