Cod sursa(job #2850725)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 17 februarie 2022 14:17:46
Problema Tunelul groazei Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>

using namespace std;

#pragma GCC optimize ("Ofast")

ifstream fin("tunel.in");
ofstream fout("tunel.out");

struct nodul {
    int nod, cost;
};

const double eps = 0.0001;
int n, m;
double mat[260][260], sol[260];
vector <nodul> G[260];

void schimb(int a, int b)
{
    for(int i = 1; i <= n; i++)
        swap(mat[a][i], mat[b][i]);
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        G[x].push_back({y, c});
        G[y].push_back({x, c});
    }
    for(int nod = 1; nod < n; nod++)
    {
        int nr_vec = G[nod].size(), total = 0;
        for(nodul vecin : G[nod])
        {
            total += vecin.cost;
            if(vecin.nod != n)
                mat[nod][vecin.nod] += (double) 1 / nr_vec;
        }
        mat[nod][nod] = -1;
        mat[nod][n] = - (double) total / nr_vec;
    }
    n--, m = n;
    int i = 1, j = 1;
    while(i <= n && j <= m)
    {
        int k;
        for(k = i; k <= n; k++)
            if(mat[k][j] < -eps || mat[k][j] > eps)
                break;
        if(k == n + 1)
        {
            j++;
            continue;
        }
        if(k != i)
            schimb(k, i);
        for(k = j + 1; k <= m + 1; k++)
            mat[i][k] = mat[i][k] / mat[i][j];
        mat[i][j] = 1;
        for(k = i + 1; k <= n; k++)
        {
            for(int l = j + 1; l <= m + 1; l++)
                mat[k][l] -= mat[k][j] * mat[i][l];
            mat[k][j] = 0;
        }
        i++, j++;
    }
    for(i = n; i > 0; i--)
    {
        for(int j = 1; j <= m + 1; j++)
        {
            if(mat[i][j] > eps || mat[i][j] < -eps)
            {
                if(j == m + 1)
                {
                    fout << "Imposibil";
                    return 0;
                }
                sol[j] = mat[i][m + 1];
                for(int k = j + 1; k <= m; k++)
                    sol[j] -= sol[k] * mat[i][k];
                break;
            }
        }
    }
    fout << fixed << setprecision(3) << sol[1] << '\n';
    return 0;
}