4003.基于Dijsktra算法的最短路径求解

基于Dijsktra算法的最短路径求解

发布时间: 2018年11月26日 10:14 时间限制: 1000ms 内存限制: 128M

有趣的最短路...火候欠佳，目前还很难快速盲打出来，需继续练习。

描述

一张地图包括n个城市，假设城市间有m条路径（有向图），每条路径的长度已知。给定地图的一个起点城市和终点城市，利用Dijsktra算法求出起点到终点之间的最短路径。

输入

多组数据，每组数据有m+3行。第一行为两个整数n和m，分别代表城市个数n和路径条数m。第二行有n个字符，代表每个城市的名字。第三行到第m+2行每行有两个字符a和b和一个整数d，代表从城市a到城市b有一条距离为d的路。最后一行为两个字符，代表待求最短路径的城市起点和终点。当n和m都等于0时，输入结束。

输出

每组数据输出两行。第一行为一个整数，为从起点到终点之间最短路的长度。第二行为一串字符串，代表该路径。每两个字符之间用空格隔开。

样例输入1

3 3
A B C
A B 1
B C 1
A C 3
A C
6 8
A B C D E F
A F 100
A E 30
A C 10
B C 5
C D 50
E D 20
E F 60
D F 10
A F
0 0

样例输出1

2
A B C
60
A E D F

 1 #include<iostream>
 2 using namespace std;
 3 #define maxn 200
 4 #define inf 1e9
 5 
 6 int n;
 7 char v[maxn];//v[A]==1;
 8 int Hash[maxn];//build char index's hash list <char,int>
 9 int e[maxn][maxn];//direct distance between two point
10 int dis[maxn];//dis from start
11 int path[maxn];//path=point which is the passing
12 int visit[maxn];//1 present has visited
13 
14 void Dijkstra(int x)
15 {//x is start
16     int k, min;
17     for (int i = 1; i <= n; i++)
18     {
19         dis[i] = e[x][i];
20         visit[i] = 0;//
21         if (e[x][i]<inf)
22             path[i] = x;//add new point into path
23         else
24             path[i] = -1;//this point doesn't inter the path
25     }
26     dis[x] = 0;//the dis from itself to isself is 0
27     visit[x] = 1;//has visited
28     for (int t = 0; t<n - 1; t++)
29     {
30         min = inf;
31         for (int i = 1; i <= n; i++)
32         {
33             if (!visit[i] && dis[i]<min)//has visited and short dis
34             {
35                 k = i;
36                 min = dis[i];
37             }
38         }
39         visit[k] = 1;//k shortest point
40         for (int i = 1; i <= n; i++)
41         {
42             if (!visit[i] && dis[i]>dis[k] + e[k][i])//through k to this point is shorter
43             {
44                 dis[i] = dis[k] + e[k][i];
45                 path[i] = k;
46             }
47         }
48     }
49 }
50 void printpath(int x)
51 {
52     if (x != -1)
53     {
54         printpath(path[x]);
55         cout<<v[x]<<" ";
56     }
57 }
58 int main()
59 {
60     int m, d;
61     char x, y;
62     while (1)
63     {
64         cin>>n>>m;
65         if (!n&&!m)break;
66         for (int i = 0; i<maxn; i++)
67             for (int j = 0; j<maxn; j++)
68                 e[i][j] = inf;
69         for (int i = 1; i <= n; i++)//from 1
70         {
71             cin>>v[i];
72             Hash[v[i]] = i;//build char index's hash list <char,int>
73         }
74         while (m--)
75         {
76             cin>>x>>y>>d;
77             e[Hash[x]][Hash[y]] = e[Hash[y]][Hash[x]] = d;//change to邻接矩阵
78         }
79         cin >> x >> y;
80         Dijkstra(Hash[x]);//input start point..
81         cout<<dis[Hash[y]]<<endl;//after renew,output dis...
82         printpath(path[Hash[y]]);//output path
83         cout<<v[Hash[y]]<<endl;//output last path
84     }
85     return 0;
86 }