Cod sursa(job #2071258)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 20 noiembrie 2017 15:21:31
Problema Tunelul groazei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include<fstream>
#include<vector>
#include<iomanip>
#define f first
#define s second
#define eps 0.000000001
using namespace std;
int n, m, i, j, ii, jj, x, y, z;
int g[260];
double val[260], a[260][260];
vector< pair<int, int> > v[260];
ifstream fin("tunel.in");
ofstream fout("tunel.out");
int main(){
    fin>> n >> m;
    for(i = 1; i <= m; i++){
        fin>> x >> y >> z;
        g[x]++;
        g[y]++;
        v[x].push_back( make_pair(y, z) );
        v[y].push_back( make_pair(x, z) );
    }
    for(i = 1; i < n; i++){
        a[i][i] = -1;
        for(j = 0; j < v[i].size(); j++){
            a[i][ v[i][j].f ] += 1.0 / g[i];
            a[i][n + 1] -= (1.0 / g[i]) * v[i][j].s;
        }
    }
    i = j = 1;
    while(i < n && j <= n){
        for(ii = i; ii < n; ii++){
            if(a[ii][j] > eps || a[ii][j] < -eps){
                break;
            }
        }
        if(ii == n){
            j++;
            continue;
        }
        if(ii != i){
            for(jj = j; jj <= n + 1; jj++){
                swap(a[ii][jj], a[i][jj]);
            }
        }
        for(jj = j + 1; jj <= n + 1; jj++){
            a[i][jj] /= a[i][j];
        }
        a[i][j] = 1;
        for(ii = i + 1; ii < n; ii++){
            for(jj = n + 1; jj >= j; jj--){
                a[ii][jj] -= a[i][jj] * a[ii][j];
            }
        }
        i++;
        j++;
    }
    for(i = n - 1; i >= 1; i--){
        for(j = 1; j < n; j++){
            if(a[i][j] > eps || a[i][j] < -eps){
                break;
            }
        }
        if(j != n){
            val[j] = a[i][n + 1];
            for(jj = j + 1; jj <= n; jj++){
                val[j] -= a[i][jj] * val[jj];
            }
        }
    }
    fout<< setprecision(4) << fixed << val[1] <<"\n";
    return 0;
}