Evtyukhov_Tipovik4_ex7c

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,popcnt,tune=native")
#pragma GCC target("avx,avx2")
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <windows.h>
using namespace std;
int n = 6;
int m = 12;
int INF = 1e9 - 1;
int graph[6][6]; //задали и считали граф

vector<int> Djikstra (int s){
    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 < n; ++j){
            if (graph[v][j] != INF && graph[v][j] != 0){
                if (d[v] + graph[v][j] < d[j]) {
                    d[j] = d[v] + graph[v][j];
                    p[j] = v;
                }
            }
        }
    }
    return d;

}


int main(){

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            graph[i][j] = INF;
        }
    }
    for (int i = 0; i < n; i++)
        graph[i][i] = 0;


    for (int i = 0; i < m; i++){
        int x, y, w;
        cin >> x >> y >> w;
        x--;
        y--;
        graph[x][y] = w;
        graph[y][x] = w;
    }

    vector<int> ans = Djikstra(3);
    for (auto x: ans) cout << x << endl;

}

/*
1 2 2
1 5 6
1 6 2
2 3 2
2 4 4
2 6 4
3 4 7
3 5 5
3 6 5
4 5 4
4 6 6
5 6 2
*/