一个人的旅行(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 ;
}