Submission #3891

#TimeUsernameProblemLanguageResultExecution timeMemory
3891waps12bFollowing Flow (kriii1_F)C++98
0 / 1
4 ms8192 KiB
#include<cstdio> #include<queue> #include<vector> #include<algorithm> using namespace std; int v[31][1001]; double dist[31][1001]; int cnt[31]; struct Q{ double per; double dist; int pos; int len; Q(int pos_,double dist_,double per_,int len_){ pos = pos_; dist = dist_; per = per_; len = len_; } }; double sum=0; int main(){ int lmt = 500; int n, m;scanf("%d %d",&n,&m); for(int i=0;i<m;i++){ int a, b; double t; scanf("%d %d %lf",&a,&b,&t); v[a][ cnt[a] ] = b; dist[a][ cnt[a] ] = t; cnt[a] ++; } queue<Q> q; q.push(Q(0,0,1,0)); while(q.size()){ Q now = q.front(); q.pop(); if(now.pos== n){ sum += now.dist * now.per; continue; } if(cnt[now.pos] == 0 || now.len > lmt) continue; double per = now.per / (double)cnt[now.pos]; for(int i=0;i<cnt[now.pos];i++) q.push(Q( v[now.pos][i] , now.dist + dist[now.pos][i] , per,now.len + 1)); } printf("%.10lf\n",sum); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...