起点终点未定的最短路径——ACM_HongKong D题

题目地址

ACM 2017 Asia HongKong D题

题目大意：

求某两个点之间的最短距离，起点为a，终点为b,然后，求两个点之间的最短距离。

算法思路：

• 本题采用迪杰斯特拉算法求最短路径。
• 由于迪杰斯特拉算法的特性，求所有终点的最短路径好求。
• 关键是不定起点的要求。
• 不过代码还是很好改。
• 算是模板题了

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#define inf 1<<29
#define MAXV 51
using namespace std;
int map[51][51];
int n;
int a,b;
//相当于2的29次方
//相当于无限大
void dijkstra(int a,int b){
    int i,j,min,v;
    int d[MAXV];//最短路径
    bool vis[MAXV];
    //记录该点是否已经加入了图中
    for(i=1;i<=n;i++){
        vis[i]=0;
        d[i]=map[a][i];
        //不定长度需要修改的地方1
    }
//初始化所有的点到起点的距离
    for(i=1;i<=n;i++){
        min=inf;//初始化为无穷大
        for(j=1;j<=n;j++)
            if(!vis[j] && d[j]<min){
              //如果该点还不在整个最短路径途中
              //如果该点到起始点的距离为
                v=j;//找的路径最短的点
                min=d[j];//设置最短路径
            }//寻找在这个图的规模中的最短路径
        vis[v]=1;
       //设置为已找到
        for(j=1;j<=n;j++)
            if(!vis[j] && d[j]>map[v][j]+d[v])//更新条件
            //1.还没找到最短路径
            //2.dj比新找到的点的最短路径加上到新加的点的最短路径的和要短
                d[j]=map[v][j]+d[v];//更新dj
    }//所有点的最短路径都找到了
    //输出到最后一个点的最短距离
    printf("%d\n",d[b]);
    //需要修改的地方2
}
int main()
{
    int i,j;
    int x,y,len;
    while(cin>>n){
      cin>>a>>b;
      for(i=1;i<=n;i++)
            for(j=1;j<=n;j++){
                if(i==j){
                    map[i][i]=0;}//从一个点到这个点本身的最短距离为零
                else {map[i][j]=map[j][i]=inf;}}//初始化为无穷大
//相当于memset函数的作用
      while(cin>>x&&x!=0){
        cin>>y>>len;
         if(map[x][y]>len) map[x][y]=map[y][x]=len;//赋值
      }
      dijkstra(a,b);
    }
    return 0;
}