首页 > 代码库 > 去北京看奥运
去北京看奥运
去北京看奥运
Time Limit: 1 Sec Memory Limit: 64 MBSubmit: 1080 Solved: 506
Description
2008年将到，王飞同学化了九牛二虎之力搞到了2张2008年奥运会足球赛决赛的门票。真是开心啊！他爸爸准备开车跟他一起去北京看球赛。不过门票费好贵啊，所以他爸爸说了，这个钱要在下学期的生活费里扣（好抠门），不过如果他能让从杭州去北京的油费最省（油价最近涨的好厉害啊），那么就不扣生活费了。哈哈，这个就难不倒他了。在ACM里可不是白混的。很快他算出了汽车从杭州到北京必须要加几次油，并查出了到北京要经过哪几个城市，每个城市有哪些加油站以及从某城市各加油站到另一城市各加油站的距离和路况算出了各加油站之间的耗油量。下面是不是很easy?
Input
有多个测试案例。第一行先输入测试案例的数目T。对于每个测试案例，第一行输入一个整数n表示将在中途n（0 < n < 40)个城市中加油，后面紧跟着是n个整数代表每个城市有几个加油站(每个城市加油站不超过10个）。以下n+1行，每行由3个Si,Ej,L一组组成的好几对整数，该行以0结束。表示从前一城市Si第i个加油站（杭州的话就是家拉）出发到该城市第j个加油站消耗的油量为L升。
Output
对于每个测试，输出一行，内容为最小总耗油量。
Sample Input
12 2 31 1 3 1 2 1 01 1 2 1 2 7 2 1 8 2 2 9 2 3 4 01 1 5 2 1 6 3 1 6 0
Sample Output
10
1 #include<stdio.h> 2 #include<string.h> 3 #define max 9999999 4 5 int map[500][500]; 6 int vis[500],dis[500]; 7 int sum; 8 9 void dijkstra(int cost[][500],int n)10 {11 int i,j,k,minc;12 memset(vis,0,sizeof(vis));13 dis[0]=0;14 vis[0]=1;15 for(i=1;i<n;i++)dis[i]=cost[0][i];16 for(i=1;i<n;i++)17 {18 minc=max;19 for(j=0;j<n;j++)20 if(!vis[j]&&dis[j]<minc)21 {22 minc=dis[j];23 k=j;24 }25 if(minc==max)26 break;27 vis[k]=1;28 for(j=0;j<n;j++)29 if(!vis[j]&&dis[j]>dis[k]+cost[k][j])30 {31 dis[j]=dis[k]+cost[k][j];32 }33 }34 // for(i=0;i<n;i++)35 // printf("%d ",dis[i]);dis[]保存到每一个点的最短路36 printf("%d\n",dis[n-1]);37 }38 int main()39 {40 //freopen("a.txt","r",stdin);41 int t,n,city[50];42 int s,e,l,j,i,tot;43 scanf("%d",&t);44 while(t--)45 {46 scanf("%d",&n);47 city[0]=0,city[1]=1;48 sum=0;49 tot=2;50 for(i=2;i<=n+1;i++)51 {52 scanf("%d",&city[i]);53 tot+=city[i];54 }55 for(i=0;i<tot;i++)56 for(j=0;j<tot;j++)57 {58 map[i][j]=max;59 }60 for(i=2;i<=n+2;i++)61 {62 sum+=city[i-2];63 while(scanf("%d",&s)==1&&s)64 {65 scanf("%d%d",&e,&l);66 map[sum+s-1][sum+city[i-1]+e-1]=l;67 }68 }69 70 dijkstra(map,tot);71 }72 return 0;73 }
去北京看奥运
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。