Аврора Интенсив день4

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include <cmath>
#include <math.h>
#include <algorithm>
#include <map>
#include <vector>
#include <utility>
#include <set>
#include <string>
#include <cstring>
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <bitset>
#include <cassert>
#include <functional>
//#include <intrin.h>
#include <stack>
#include <thread>
using namespace std;
//typedef long long ll;
#define ll long long
#define ld long double

const long long mod = 1000000007;

#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)>(y)?(x):(y))
#define PI 3.14159265358979323846
#define ABS(a) ((a)<0?-(a):(a))
template <typename T> inline T gcd(T a, T b) {
    while (b) { a %= b; swap(a, b); }
    return a;
}
long long fastpow(long long a, long long n)
{
    auto mult = a;
    long long res = 1;
    while (n)
    {
        if (n & 1)
            res *= mult;
        mult *= mult;
        n >>= 1;
    }
    return res;
}

void LCS()
{
    string a, b;
    cin >> a >> b;
    vector<vector<int>> ans_matr(a.size() + 1);
    ans_matr[0].resize(b.size() + 1, 0);
    for (int i = 0; i < a.size(); i++)
    {
        ans_matr[i + 1].resize(b.size() + 1, 0);
        for (int j = 0; j < b.size(); j++)
            if (a[i] == b[j])
                ans_matr[i + 1][j + 1] = ans_matr[i][j] + 1;
            else
                ans_matr[i + 1][j + 1] = max(ans_matr[i][j + 1], ans_matr[i + 1][j]);
    }
    cout << ans_matr[a.size()][b.size()] << endl;
    string ans = "";
    int i = a.size();
    int j = b.size();
    while (i && j)
    {
        while (i && ans_matr[i - 1][j] == ans_matr[i][j])
            i--;
        while (j && ans_matr[i][j - 1] == ans_matr[i][j])
            j--;
        if (i && j)
        {
            ans.push_back(a[i - 1]);
            i--;
            j--;
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans;
}

void MaxPalindromeSubseq()
{
    string s;
    cin >> s;
    vector<vector<int>> matr_res(s.size());
    for (int i = 0; i < s.size(); i++)
    {
        matr_res[i].resize(s.size() + 1, 0);
        matr_res[i][i + 1] = 1;
    }
    for (int ni = 1; ni < s.size(); ni++)
    {
        for (int nj = ni; nj < s.size(); nj++)
        {
            int i = nj - ni;
            int j = nj + 1;
            if (s[i] == s[j - 1])
            {
                matr_res[i][j] = matr_res[i + 1][j - 1] + 2;
            }
            else
                if (i < s.size() - 1)
                    matr_res[i][j] = max(matr_res[i + 1][j], matr_res[i][j - 1]);
                else
                    matr_res[i][j] = matr_res[i][j - 1];
        }
    }
    string ans;
    int i = 0, j = s.size();
    while (matr_res[i][j])
    {
        while (matr_res[i][j - 1] == matr_res[i][j])
            j--;
        while (i < s.size() - 1 && matr_res[i + 1][j] == matr_res[i][j])
            i++;
        ans.push_back(s[i]);
        j--;
        i++;
    }
    string rev_ans = ans;
    reverse(rev_ans.begin(), rev_ans.end());
    if (matr_res[0][s.size()] % 2)
    {
        ans.pop_back();
    }
    cout << ans + rev_ans << endl;
}

void Dijkstra()
{
    int n, m, a, b, c;
    cin >> n >> m;
    vector<int> dist(n, INT32_MAX), from(n, -1), passed(n, 0);
    vector<vector<pair<int, int>>> neighbours(n);
    dist[0] = 0;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        a--, b--;
        neighbours[a].push_back({ b,c });
        neighbours[b].push_back({ a,c });
    }
    for (int t = 0; t < n; t++)
    {
        int mindist = INT32_MAX;
        int mini = -1;
        for (int i = 0; i < n; i++)
            if (!passed[i])
            {
                if (dist[i] < mindist)
                {
                    mindist = dist[i];
                    mini = i;
                }
            }
        if (mini < 0)
            break;
        passed[mini] = 1;
        for (auto& p : neighbours[mini])
        {
            if (dist[mini] + p.second < dist[p.first])
            {
                dist[p.first] = dist[mini] + p.second;
                from[p.first] = mini;
            }
        }
    }
    cin >> a;
    a--;
    vector<int> v_ans;
    int d_ans = dist[a];
    v_ans.push_back(a);
    while (from[a] >= 0)
    {
        v_ans.push_back(from[a]);
        a = from[a];
    }
    reverse(v_ans.begin(), v_ans.end());
    cout << d_ans << " " << v_ans.size() << endl;
    for (auto& a : v_ans)
        cout << a + 1 << " ";

}

void DijkstraFast()
{
    int n, m, a, b, c;
    cin >> n >> m;
    vector<int> dist(n, INT32_MAX), from(n, -1), passed(n, 0);
    vector<vector<pair<int, int>>> neighbours(n);
    dist[0] = 0;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        a--, b--;
        neighbours[a].push_back({ b,c });
        neighbours[b].push_back({ a,c });
    }
    set<pair<int, int>> nxt;
    nxt.insert({ 0,0 });
    for (int t = 0; t < n; t++)
    {
        if (nxt.empty())
            break;
        int mindist;
        int mini;
        tie(mindist, mini) = *(nxt.begin());
        passed[mini] = 1;
        for (auto& p : neighbours[mini])
        {
            if (dist[mini] + p.second < dist[p.first])
            {
                if (dist[p.first] != INT32_MAX)
                    nxt.erase({ dist[p.first],p.first });
                dist[p.first] = dist[mini] + p.second;
                from[p.first] = mini;
                nxt.insert({ dist[p.first],p.first });
            }
        }
    }
    cin >> a;
    a--;
    vector<int> v_ans;
    int d_ans = dist[a];
    v_ans.push_back(a);
    while (from[a] >= 0)
    {
        v_ans.push_back(from[a]);
        a = from[a];
    }
    reverse(v_ans.begin(), v_ans.end());
    cout << d_ans << " " << v_ans.size() << endl;
    for (auto& a : v_ans)
        cout << a + 1 << " ";

}

void Ford_Bellman(int v, int u, int n, vector<pair<pair<int, int>, int>> edges)
{
    vector<int> d(n, INT32_MAX);
    vector<int> p(n, -1);
    d[v] = 0;
    int i = 0;
    int change = -1;
    for (; i < n; i++)
    {
        change = -1;
        for (auto& a : edges)
        {
            if (d[a.first.first] != INT32_MAX && d[a.first.first] + a.second < d[a.first.second])
            {
                change = a.first.second;
                p[a.first.second] = a.first.first;
                d[a.first.second] = d[a.first.first] + a.second;
            }
        }
        if (change < 0)
            break;
    }
    if (i == n)
    {
        cout << "negative loop detected" << endl;//цикл можно восстановить если использовать p как рёбра графа и искать цикл обходом из change
        return;
    }
    if (d[u] == INT32_MAX)
    {
        cout << "destination unreachable" << endl;
        return;
    }
    cout << d[u] << ' ';
    vector<int> ans = { u };
    int c = u;
    while (p[c] >= 0)
    {
        ans.push_back(p[c]);
        c = p[c];
    }
    cout << ans.size() << endl;
    reverse(ans.begin(), ans.end());
    for (auto& a : ans)
        cout << a << ' ';
}

int start = -1;
vector<int>  cycle;

void FindCycle(vector<vector<bool>>& matr, vector<bool>& passed, int i)
{
    passed[i] = true;
    for (int j = 0; j < matr[i].size(); j++)
    {
        if (matr[i][j])
        {
            if (!passed[j])
            {
                FindCycle(matr, passed, j);
            }
            else
            {
                start = j;
            }
        }

        if (start >= 0)
        {
            cycle.push_back(i);
            if (start == i)
            {
                start = -1;
            }
            return;
        }
        if (cycle.size())
            return;
    }
}

vector<vector<int>> d;
vector<vector<int>> p;
int n;
void Floyd_Warshall()//INT32_MAX
{
    for (int t = 0; t < n; t++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (d[i][t] != INT32_MAX && d[t][j] != INT32_MAX)
                {
                    if (d[i][t] + d[t][j] < d[i][j])
                    {
                        d[i][j] = d[i][t] + d[t][j];
                        p[i][j] = t;
                    }
                }
}

void GetFloyd_WarshallPath(vector<int>& path, int i, int j)
{
    if (p[i][j] < 0)
        return;
    GetFloyd_WarshallPath(path, i, p[i][j]);
    path.push_back(p[i][j]);
    GetFloyd_WarshallPath(path, p[i][j], j);
}

void GetFloyd_WarshallPathStart(vector<int>& path, int i, int j)
{
    path.push_back(i);
    GetFloyd_WarshallPath(path, i, j);
    path.push_back(j);
}

bool CheckIfBinaryGraph(vector<vector<bool>>& matr, vector<int>& passed)
{
    queue<int> que;
    passed.clear();
    passed.resize(matr.size(), -1);
    for (int i = 0; i < matr.size(); i++)
    {
        que.push(i);
        passed[i] = 0;
        while (que.size())
        {
            int ti = que.front();
            que.pop();
            for (int j = 0; j < matr[ti].size(); j++)
                if (matr[ti][j])
                    if (passed[j] < 0)
                    {
                        passed[j] = 1 - passed[ti];
                        que.push(j);
                    }
                    else
                        if (passed[ti] == passed[j])
                            return false;
        }
    }
    return true;
}

int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    Dijkstra();
    return 0;
}