赤祼祼的源点到终点的最短路(dijkstra算法)hdu1874

Problem Description

某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。

现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。

 

Input

本题目包含多组数据，请处理到文件结束。
每组数据第一行包含两个正整数N和M(0接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B再接下一行有两个整数S,T(0<=S,T

 

Output

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

 

Sample Input

(n,m)n个城镇，已经存在的m条路，
3 3
0 1 1
0 2 3
1 2 1
0 2(s->dist)

3 1
0 1 1
1 2

Sample Output

2
-1

总是超时！！

#include <stdio.h>

#define MAX 99999
#define LEN 1009

int map[LEN][LEN];    //某点到某点两点间的的距离
int dist[LEN];        //记录当前点到源点的最短路径长度
int mark[LEN];        //加入进来的点的集合



    //初始化map为正无穷大
    void init()
    {
       int i,j;
       for(i=0;i<LEN;i++)
       {
              for(j=0;j<LEN;j++)
              {
                     map[i][j]=MAX;
              }
       }
    }

    //n:多少条路  start:起始点
    //dist[i],最后存储着start 到i点的最短距离
    int myDijstra(int n,int start)
    {
       int i,j,min,pos;
       for(i=0;i<=n-1;i++)
       {
            mark[i]=0;//没有点加入
            dist[i]=map[start][i];//把start 附近点 dis[]初始化
       }

       mark[start]=1;//把起始点加进来
       dist[start]=0;

       for(i=0;i<n-1;i++)//注意i<n-1
       {
              min=MAX;
              pos=-1;
              for(j=0;j<=n-1;j++)
              {
                     if(!mark[j] && dist[j]<min)
                     {    //取出不在mark里的最小的dist[i]
                         min=dist[j];
                         pos=j;//标记
                     }

              }

              //if(min==MAX)//已经不能通了
             // printf("%d\n",pos);
              if(pos==-1)
                  return -1;

                mark[pos]=1;//把K加进来

              //做松弛操作
              for(j=0;j<=n-1;j++)
              {
                    if(!mark[j] && dist[j]>dist[pos]+map[pos][j])//start->j or start->pos,pos->j
                    {
                       dist[j]=dist[pos]+map[pos][j];//这步跟prim算法有点不同
                    }
              }
        }
       return 1;
    }



int main()
{

       int i,n,line;
       int a,b,d;
    while(scanf("%d%d",&n,&line)!=EOF)
    {
        //scanf("%d%d",&n,&line);//输入点和
        init();
        for(i=0;i<line;i++)
        {

            scanf("%d%d%d",&a,&b,&d); //输入各边的权值
            if(map[a][b]>d)//防止重边,(1 2 4)(1 2 5)
            {
            map[a][b]=map[b][a]=d;
            }


        }
        int s,d;
        scanf("%d%d",&s,&d);
            int ans=myDijstra(n,s);//调用方法(点数，起始点)

        //输出s到d的最短路径
            if(ans==-1)
                printf("-1\n");
            else
                printf("%d\n",dist[d]);


    }
       return 0;

}

阅读(1059) | 评论(0) | 转发(0) |

0

上一篇：单源最短路径问题[Dijkstra实现](邻接矩阵)

下一篇：在一百万数字中求最大的10个数字的算法