HDU1874 畅通工程续
来源：程序员人生 发布时间：2015-02-04 09:06:46 阅读次数：2909次
链接：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
*/
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
