首页 > 代码库 > HDU1874 畅通工程续

HDU1874 畅通工程续

2024-11-13 15:56:02   204人阅读

链接：click here

题意：

某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。
 
Input
本题目包含多组数据，请处理到文件结束。
每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。
接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。
 
Output
对于每组数据，请在一行里输出最短需要行走的距离。如果不存在从S到T的路线，就输出-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]);
        }
    }                                 //原先一贯的写法，测试发现效率不是很高
//    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("-1\n");
    else printf("%d\n",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
*/



HDU1874 畅通工程续


联系
我们