Pagini recente » Cod sursa (job #2304741) | Cod sursa (job #2051726) | Cod sursa (job #1875666) | Cod sursa (job #1897129) | Cod sursa (job #1663898)
#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;
}