分析:
这道题其实是最小比例生成树。但是呢。我不知道的正解写法。于是呢,所以。用了一种奇技淫巧。因为这里是有向无环图。这个我们在这里可以用最短路的想法。spfa是个好东西。由题目可以得知。这道题其实就是想让我们求1~n所有路径里,(一条路径里)每条路的平均值最小。所以我们这里其实就是要求出每条路的最短路。。其实就是每次用多少边走下来的最短路。可能有些边数也走不到。那么把所有的这个边求出来,最后算平均值就好。
所以我们设d[i][j]是第i个点从起点走了j条边到达的最短路。visit[i][j]与前面对应。就是这样。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include<cstdio> #include<algorithm> #include<string.h> #define MAX_1 10611109567 using namespace std; struct node{ int v,next,val; }edge[100010]; struct que{ int num,step; }; que q[100010]; int d[210][2100],visit[210][2100],cnt,head[2010]; int n,m; void spfa() { que news; news.step=1;news.num=1; memset(d,0x3f,sizeof(d)); int heads=1,last=1; d[1][1]=0; q[heads]=news; while(heads<=last) { que first=q[heads]; for(int i=head[first.num];i!=-1;i=edge[i].next) { if(d[edge[i].v][first.step+1]>d[first.num][first.step]+edge[i].val){ d[edge[i].v][first.step+1]=d[first.num][first.step]+edge[i].val; if(visit[edge[i].v][first.step+1])continue; visit[edge[i].v][first.step+1]=1; que l; l=(que){edge[i].v,first.step+1}; q[++last]=l; } } visit[first.num][first.step]=0; ++heads; } return ; } void address(int x,int y,int val) { edge[++cnt].v=y; edge[cnt].next=head[x]; edge[cnt].val=val; head[x]=cnt; } int main() { freopen("calabash.in","r",stdin); freopen("calabash.out","w",stdout); memset(head,-1,sizeof(head)); int x,y,val; scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) { scanf("%d%d%d",&x,&y,&val); address(x,y,val); } spfa(); double ans=99999999.0; for(int i=2;i<=n;++i) { if(d[n][i]<MAX_1)ans=min(ans,(double)d[n][i]/i); } printf("%.3lf",ans); fclose(stdin); fclose(stdout); return 0; } |