Cod sursa(job #1663898)

Utilizator DysKodeTurturica Razvan DysKode Data 26 martie 2016 11:22:56
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.37 kb
#include <fstream>
#include <list>
#include <queue>
#include <vector>
#include <iomanip>

using namespace std;

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

#define cost second
#define N 100010
#define urm first

vector< int > v[N],g[N];
queue <int> q;
long long a,b,c,i,j,n,m,cost[N],moduri[N],x,y,modurig[N],now,mod,total,st[N],grad[N],gradg[N],stg[N];
long double ans;

int main()
{
    fin >> n >> m >> a >> b;
    for(i = 1; i <= n; i++)
        fin >> cost[i];
    for(i = 1; i <= m; i++)
    {
        fin >> x >> y;
        v[x].push_back(y);
        g[y].push_back(x);
    }
    q.push(a);
    st[a] = 1;
    while(q.size())
    {
        now = q.front();
        q.pop();
        for(i = 0; i < v[now].size(); i++)
        {
            grad[ v[now][i] ] ++;
            if(st[ v[now][i] ] == 0)
            {
                st[ v[now][i] ] = 1;
                q.push(v[now][i]);
            }
        }
    }
    q.push(b);
    stg[b] = 1;
    while(q.size())
    {
        now = q.front();
        q.pop();
        for(i = 0; i < g[now].size(); i++)
        {
            gradg[g[now][i]] ++;
            if(stg[ g[now][i] ] == 0)
            {
                stg[ g[now][i] ] = 1;
                q.push(g[now][i]);
            }
        }
    }



    q.push(a);
    moduri[a] = 1;
    while(q.size())
    {
        now = q.front();
        q.pop();
        for(i = 0; i < v[now].size(); i++)
        {
            moduri[ v[now][i] ] += moduri[now];
            grad[v[now][i]]--;
            if(grad[ v[now][i] ] == 0)
            {
                q.push(v[now][i]);
            }
        }
    }
    total = moduri[b];
    if(total == 0)
    {
        fout<<0;return 0;
    }
    q.push(b);
    modurig[b] = 1;
    while(q.size())
    {
        now = q.front();
        q.pop();
        for(i = 0; i < g[now].size(); i++)
        {
            modurig[ g[now][i] ] += modurig[now];
            gradg[ g[now][i] ] --;
            if(gradg[ g[now][i] ] == 0)
            {
                q.push(g[now][i]);
            }
        }
    }
    for(i = 1; i <= n; i++)
    {
        if(moduri[i] && modurig[i])
        {
            ans += (moduri[i] * modurig[i]) * cost[i] * 1.0 / total;
        }
    }
    fout<<setprecision(10);
    fout<<fixed;
    fout<<ans;

return 0;
}