Cod sursa(job #1830494)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 16 decembrie 2016 19:51:30
Problema Tunelul groazei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 260;
const double eps = 1e-7;

int n, m, x, y, t, i, j, k, nr, sum, p;
double a[Nmax][Nmax], coef;
vector< pair<int,int> > v[Nmax];

bool nenul(double x)
{
    return x>eps || x<-eps;
}

int main()
{
    freopen("tunel.in", "r", stdin);
    freopen("tunel.out", "w", stdout);

    scanf("%d%d", &n, &m);

    for(i=1; i<=m; ++i)
    {
        scanf("%d%d%d", &x, &y, &t);
        v[x].push_back({y,t});
        v[y].push_back({x,t});
    }

    for(i=1; i<n; ++i)
    {
        sum = 0; nr = v[i].size();

        for(auto it : v[i])
            sum += it.second;

        for(auto it : v[i])
            a[i][it.first] -= 1.0;

        a[i][i] = nr*1.0;
        a[i][n] = sum*1.0;
    }

    for(i=1; i<n; ++i)
    {
        for(p=1; p<n; ++p)
            if(nenul(a[i][p])) break;

        for(j=1; j<n; ++j)
        if(i!=j && nenul(a[j][p]))
        {
            coef = a[j][p] / a[i][p];
            for(k=1; k<=n; ++k)
                a[j][k] -= coef * a[i][k];
        }
    }

    for(i=1; i<=n; ++i)
        if(nenul(a[i][1]))
            printf("%.3lf\n", a[i][n] / a[i][1]);

    return 0;
}