学步园

题目连接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=12&problem=1040&mosmsg=Submission+received+with+ID+8760564

这个题很YD,之前一直不知道导游还要占一个容量，所以连样例都搞不懂。。悲催。。

解法是利用floyd算法，最后求出那条边之后再做一下出发就OK了

我的代码：

#include<stdio.h><br /> #include<algorithm><br /> #include<string.h></p> <p>using namespace std;</p> <p>int n,m;<br /> int dis[105][105];</p> <p>int max(int a,int b)<br /> {<br /> if(a>b)<br /> return a;<br /> else<br /> return b;<br /> }</p> <p>int min(int a,int b)<br /> {<br /> if(a>b)<br /> return b;<br /> else<br /> return a;<br /> }</p> <p>int main()<br /> {<br /> int i,j,a,b,c,k,t=1;<br /> int start,end,people;<br /> while(scanf("%d%d",&n,&m)!=EOF)<br /> {<br /> if(n==0&&m==0)<br /> break;<br /> memset(dis,0,sizeof(dis));<br /> for(i=1;i<=m;i++)<br /> {<br /> scanf("%d%d%d",&a,&b,&c);<br /> dis[a][b]=c;<br /> dis[b][a]=c;<br /> }<br /> scanf("%d%d%d",&start,&end,&people);<br /> for(k=1;k<=n;k++)<br /> for(i=1;i<=n;i++)<br /> for(j=1;j<=n;j++)<br /> dis[i][j]=max(dis[i][j],min(dis[i][k],dis[k][j]));<br /> int temp=dis[start][end];<br /> printf("Scenario #%d/n",t++);<br /> if(people%(temp-1))<br /> printf("Minimum Number of Trips = %d/n",people/(temp-1)+1);<br /> else<br /> printf("Minimum Number of Trips = %d/n",people/(temp-1));<br /> printf("/n");<br /> }<br /> return 0;<br /> }