一个人的旅行（Dijkstra算法）

时间：2023-01-07 17:20:53

这道题可用Dijkstra算法，好像还有floyd等算法，慢慢研究

Description

虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗~),但是草儿仍然很喜欢旅行，因为在旅途中 会遇见很多人（白马王子，^0^），很多事，还能丰富自己的阅历，还可以看美丽的风景……草儿想去很多地方，她想要去东京铁塔看夜景，去威尼斯看电影，去阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖啡写信，去北京探望孟姜女……眼看寒假就快到了，这么一大段时间，可不能浪费啊，一定要给自己好好的放个假，可是也不能荒废了训练啊，所以草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经过，所以她只能去邻近的城市坐火车（好可怜啊~）。

Input

输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个，草儿想去的地方有D个； 
接着有T行，每行有三个整数a，b，time,表示a,b城市之间的车程是time小时；(1=<(a,b)<=1000;a,b 之间可能有多条路) 
接着的第T+1行有S个数，表示和草儿家相连的城市； 
接着的第T+2行有D个数，表示草儿想去地方。

Output

输出草儿能去某个喜欢的城市的最短时间。

Sample Input

6 2 3
1 3 5
1 4 7
2 8 12
3 8 4
4 9 12
9 10 2
1 2
8 9 10

Sample Output

9
这道题不是让你直接用Dijkstra算法，也有技巧的，找到技巧调用一次Dijkstra算法就够了
草儿的家可以设为起点，标号为0，因为草儿是到邻近的城市做车，假设邻近的城市标号为i，那么arr[0][i] = 0;
这样就不用把临近的每个城市都当起点了，
假设所有城市中最大标号为n-1；
再假设一个城市n，把这个城市作为草儿的终极目标城市，草儿的目标城市到终极目标城市的距离为0，这样只用算arr[0][n]的大小就够了
再写遍思路
步骤1：任意两个地点的距离附为正无穷，所有点标记为临时节点
　　2：起点到自身的距离附为0，起点标记为永久
　　3：录入数据，若录入的距离小于当前两点间的距离，则更新这个距离为录入的距离
　　4:找出所有临时点中距离起点最近的点k，如果这个最近距离为无穷，则break，否则把这个点标记为永久
　　5：更新其他临时点到起点的距离(更新为经过k的路径的距离与直接走到当前临时点的距离中的最短距离)
一直wrong answer原因:
　　　　　　　　　　　　1:忘记了对于同一条路，时间是双向的，arr[i][j] = arr[j][i]，初始化的时候需要注意
　　　　　　　　　　　　2：我的标记是从0到n，因为0是永久的，所以更新或者初始化的时候需要到n，包含n，但总忘记写等于号
　　　　　　　　　　　　3：定义路的条数，他家临近城市数目和目标城市的数目的时候，我用的全局变量，但是在主函数中的时候忘记了，又重新定义一遍
　　　　　　　　　　　　4：更新距离的条件是输入的时间小于原本的时间，而不是输入数据就更新
上代码及详解：
#include <stdio.h>

#include <string.h>

const int M = , INF = 0x3f3f3f;

int arr[M][M], t, s, d, n;

bool vis[M];

void Init()

{

    int a, b, time, x;

    for(int i = ; i < M; i++)

        for(int j = ; j < M; j++)//把所有的路径长度初始化为正无穷

        {

            arr[i][j] = INF;

        }

    n = ;                      //n最后存放城市的最大标号，

    for(int i = ; i <= t; i++)

    {

        scanf("%d%d%d", &a, &b, &time);

        if(arr[a][b] > time)

            arr[a][b] = arr[b][a] = time; //把所有的城市间的距离录入

        if(n < a) n = a;

        if(n < b) n = b;

    }

    n++;

    for(int i = ; i <= s; i++)

    {

        scanf("%d", &x);

        arr[][x] = arr[x][] = ; //临近城市到起点的距离为0

    }

    for(int i = ; i <= d; i++)

    {

        scanf("%d", &x);

        arr[x][n] = arr[n][x] = ;//目标城市到终极目标城市的距离为0

    }

}

void Dijkstra(int src)

{

    int tmp, k;

    memset(vis, , sizeof(vis));//把所有城市标记为临时点

    for(int i = ; i <= n; i++)

    {

        tmp = INF;

        for(int j = ; j <= n; j++)

        {

            if(tmp > arr[][j] && !vis[j])//找到所有临时城市中距离起点的最近点k

            {

                tmp = arr[][j];

                k = j;

            }

        }

        vis[k] = ; //把找到的节点标记为永久

        for(int j = ; j <= n; j++)

        {

            if(arr[][k] + arr[k][j] < arr[][j])//更新所有临时节点到起点的距离为min（arr[0][j], arr[0][k] + arr[k][j]）

                arr[][j] = arr[][k] + arr[k][j];

        }

    }

}

int main()

{

    while(~scanf("%d%d%d", &t, &s, &d))

    {

        Init();

        Dijkstra();

        printf("%d\n", arr[][n]);

    }

    return ;

}

相关文章