| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 4000 | 2013-08-31T09:55:52 Z | Qwaz | Following Flow (kriii1_F) | C++ | 0 ms | 0 KB |
#include <cstdio>
#include <vector>
#include <queue>
const int N_MAX=35, M_MAX=1020;
struct state {
int time, node;
double ratio;
bool operator < (const state &t) const {
return time*ratio > t.time*t.ratio;
}
};
struct edge {
int to, time;
};
int n, m, outCount[N_MAX];
std::vector < edge > to[N_MAX];
void input(){
scanf("%d%d", &n, &m);
int i;
for(i=0; i<m; i++){
int p, q, r;
scanf("%d%d%d", &p, &q, &r);
edge t;
t.time = r;
t.to = q;
to[p].push_back(t);
}
}
std::priority_queue < state > pq;
double res;
void solve(){
state now;
now.node = 0;
now.ratio = 1;
now.time = 0;
pq.push(now);
while(true){
now = pq.top();
pq.pop();
if(now.ratio < DBL_EPSILON)
break;
int i, size=to[now.node].size();
for(i=0; i<size; i++){
int next = to[now.node][i].to;
int edgeTime = to[now.node][i].time;
state sNext;
sNext.node = next;
sNext.ratio = now.ratio/size;
sNext.time = now.time+edgeTime;
if(next == n)
res += sNext.ratio*sNext.time;
else
pq.push(sNext);
}
}
printf("%.10lf\n", res);
}
int main(){
input();
solve();
return 0;
}