HDU1874 畅通工程续

链接:click here

题意:

某省自从实行了很多年的畅通工程计划后,终究修建了很多路。不过路多了也不好,每次要从1个城镇到另外一个城镇时,都有许多种道路方案可以选择,而某些方案要比另外一些方案行走的距离要短很多。这让行人很困扰。
现在,已知出发点和终点,请你计算出要从出发点到终点,最短需要行走多少距离。
 
Input
本题目包括多组数据,请处理到文件结束。
每组数据第1行包括两个正整数N和M(0<N<200,0<M<1000),分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0~N⑴编号。
接下来是M行道路信息。每行有3个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有1条长度为X的双向道路。
再接下1行有两个整数S,T(0<=S,T<N),分别代表出发点和终点。
 
Output

对每组数据,请在1行里输出最短需要行走的距离。如果不存在从S到T的线路,就输出⑴.

思路:这道题题面不难理解,根据自己之前的做法,却是返回超时。静下心来1番仔细检查代码后,终究发现预处理数组的进程用的方法不同,返回的时间消耗就会不1样

比如我用两个for循环就比memset函数快的多,而且还发现,不知道为何定义INF的值太大时,如果用memset函数,就会出现意想不到的毛病。不知如何理解?,如果有人看到了有甚么想法,欢迎相互交换。

参考代码:

#include <string.h>
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int Inf=0x3f3f3f3f;
const int maxn=202;
int cost[maxn][maxn]; //存图
int d[maxn]; //从s动身的最短路径
bool used[maxn]; //已使用过的图
int V,pre,last; //顶点数
int city[maxn];
void dijkstra()
{
int i,j,k;
memset(used,0,sizeof(used));
for(i=0; i<V; i++)
d[i]=cost[pre][i];
d[pre]=0;
used[pre]=true;
while(true)
{
int v=Inf;
for(int u=0; u<V; u++)
{
if(!used[u]&&(v==Inf||d[u]<d[v]))
v=u;
}
if(v==Inf) break;
used[v]=true;
for(int u=0; u<V; u++)
{
d[u]=min(d[u],d[v]+cost[v][u]);
}
} //本来1贯的写法,测试发现效力不是很高
// for(i=0; i<V; i++)
// {
// min=Inf;
// for(j=0; j<V; j++)
// if(!used[j]&&d[j]<min)
// {
// min=d[j];
// k=j;
// }
// if(min==Inf)break;
// used[k]=1;
// for(j=0; j<V; j++)
// if(!used[j]&&d[j]>d[k]+cost[j][k])
// d[j]=d[k]+cost[j][k];
// }
if(d[last]==Inf)
printf("⑴
");
else printf("%d
",d[last]);
//return d[V];
}
int main()
{
int M,i,j;
while(scanf("%d%d",&V,&M)!=EOF)
{
//memset(cost,Inf,sizeof(cost));
for(i=0; i<V; i++)
for(j=0; j<V; j++)
cost [i][j]=Inf;

int u,v,quan;
for(i=0; i<M; i++)
{
scanf("%d%d%d",&u,&v,&quan);
if(cost[u][v]>quan)
{
cost[v][u]=quan;
cost[u][v]=quan;
}
}
scanf("%d%d",&pre,&last);
dijkstra();
}
return 0;
}
测试数据
/*
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
0 0
*/

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » HDU1874 畅通工程续

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡