Cod sursa(job #1969434)

Utilizator Radu_GeorgeRadu George Radu_George Data 18 aprilie 2017 14:25:14
Problema Tunelul groazei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <bits/stdc++.h>
#define Nmax 300
#define pb push_back
#define pii pair <int,int>
#define mp make_pair
#define fi first
#define se second
#define eps 0.00001

using namespace std;

double a[Nmax][Nmax];
int n,ind[Nmax];
vector <pii> L[Nmax];

inline void swapL(int l1, int l2)
{
    if(l1==l2) return;
    for(int i=1;i<=n+1;++i) swap(a[l1][i],a[l2][i]);
}

inline void Solve_Gauss()
{
    int i=1,j=1,k,t;
    while(i<=n && j<=n)
    {
        for(k=i;k<=n && fabs(a[k][j])<eps;++k);
        if(k>n+1)
        {
            ++j; continue;
        }
        swapL(i,k);
        for(k=1;k<=n;++k)
            if(k!=i)
            {
                double d = -a[k][j]/a[i][j];
                for(t=1;t<=n+1;++t)
                    a[k][t]+=a[i][t]*d;
            }
        ind[i]=j;
        ++i; ++j;
    }
}

int main()
{
    int m,x,y,z,i;
    ifstream cin("tunel.in");
    ofstream cout("tunel.out");
    cin>>n>>m;
    while(m--)
    {
        cin>>x>>y>>z;
        L[x].pb(mp(y,z));
        L[y].pb(mp(x,z));
    }
    for(i=1;i<n;++i)
    {
        a[i][i]=1;
        for(auto it : L[i])
        {
            a[i][it.fi]-=(double)1/L[i].size();
            a[i][n+1]+=(double)it.se/L[i].size();
        }
    }
    a[n][n]=1;
    Solve_Gauss();
    for(i=1;i<=n;++i)
        if(ind[i]==1) cout<<setprecision(5)<<fixed<<a[i][n+1]/a[i][1]<<"\n";
    return 0;
}