hdu4318 Power transmission 最短路 当数据很大的时候的解决办法 一道题目的解题全过程记录

Power transmissionTime Limit: 10000/5000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 656    Accepted Submission(s): 226


Problem DescriptionInputOutputSample InputSample Output/*#include <stdio.h>int v[1003];struct st{int tt; double v;}dp[50002][52],ds[50002];int dk[50002];int end;void dj(int m,int n){ int i,j,k; int max_nu;double max;for(i=1;i<=n;i++) {v[i]=0;ds[i].v=0;} ds[m].v=1; for(i=1;i<=n;i++) { max=0; for(j=1;j<=n;j++) { if(ds[j].v>max&&v[j]==0) { max=ds[j].v; max_nu=j; } } v[max_nu]=1;int k;for(j=0;j<dk[max_nu];j++){if(v[dp[max_nu][j].tt]==0&&ds[dp[max_nu][j].tt].v<ds[max_nu].v*dp[max_nu][j].v){ ds[dp[max_nu][j].tt].v=ds[max_nu].v*dp[max_nu][j].v;}}if(max_nu==end)break; }}int main(){ int i,j,m,n,kk; int a,b,c1,c2;while(scanf("%d",&n)!=EOF){for(i=1;i<=50;i++){for(j=1;j<=n;j++){dp[j][i].v=0;}}for(i=1;i<=n;i++){ scanf("%d",&dk[i]);for(kk=0;kk<dk[i];kk++){scanf("%d%d",&a,&b);dp[i][kk].v=(double)(100-b)/100.0;dp[i][kk].tt=a;}}int st;double vau;scanf("%d%d%lf",&st,&end,&vau);dj(st,n);vau=(1-ds[end].v)*vau;printf("%.2lf\n",vau);}return 0;}*/