BJFU_数据结构习题_273基于Dijsktra算法的最短路径求解

悠悠 2022-12-23 07:06 117阅读 0赞

欢迎登录北京林业大学OJ系统  
[http://www.bjfuacm.com][http_www.bjfuacm.com]

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

**描述**  
一张地图包括n个城市，假设城市间有m条路径（有向图），每条路径的长度已知。给定地图的一个起点城市和终点城市，利用Dijsktra算法求出起点到终点之间的最短路径。  
**输入**  
多组数据，每组数据有m+3行。第一行为两个整数n和m，分别代表城市个数n和路径条数m。第二行有n个字符，代表每个城市的名字。第三行到第m+2行每行有两个字符a和b和一个整数d，代表从城市a到城市b有一条距离为d的路。最后一行为两个字符，代表待求最短路径的城市起点和终点。当n和m都等于0时，输入结束。  
**输出**  
每组数据输出两行。第一行为一个整数，为从起点到终点之间最短路的长度。第二行为一串字符串，代表该路径。每两个字符之间用空格隔开。  
**输入样例**  
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  
**输出样例**  
2  
A B C  
60  
A E D F

### 以下代码源自[基于Dijsktra算法的最短路径求解][Dijsktra] ###

#include<iostream>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<string.h>
    using namespace std;
    const int NNN = 9999999;
    int road[300][300];
    int dis[300];
    int vis[300];
    int N, M;
    int d[300];
    struct Node
    {
        
    	int num;
    	char ch;
    }node[6000];
    void DIS(int x)
    {
        
    	int i;
    	int j;
    	int ans;
    	int v;
    	ans = NNN;
    	dis[x] = 0;
    	vis[x] = 1;
    	for (i = 0; i < N; i++)
    	{
        
    		dis[i] = road[x][i];
    	}
    	for (j = 0; j < N+7; j++)
    	{
        
    		for (i = 0; i < N; i++)
    		{
        
    			if (dis[i] < ans && !vis[i])
    			{
        
    				ans = dis[i];
    				v = i;
    				
    			}
     
    		}
    		vis[v] = 1;
    		ans = NNN;
    		for (i = 0; i < N; i++)
    		{
        
    			if (dis[v] + road[v][i] < dis[i])
    			{
        
    				dis[i] = dis[v] + road[v][i];
    				d[i] = v;
    			}
    		}
    	}
    }
    void print(int n)
    {
        
    	if (d[n] == n)
    	{
        
    		cout << node[n].ch;
    		return;
    	}
    	print(d[n]);
    	cout <<" "<< node[n].ch ;
    	return;
    }
     
    int main()
    {
        
    	char ch1, ch2;
    	int i, j;
    	int a, b;
    	int x, y;
    	while (cin >> N)
    	{
        
    		a = b = x = y = 0;
    		memset(dis, NNN, sizeof(dis));
    		memset(vis, 0, sizeof(vis));
    		for (i = 0; i < 250; i++)
    			for (j = 0; j < 250; j++)
    			{
        
    				if (i != j)
    					road[i][j] = NNN;
    				else
    					road[i][j] = 0;
    			}
    		cin >> M;
    		if (N == 0 && M == 0)
    			break;
    		for (i = 0; i < N; i++)
    		{
        
    			cin >> node[i].ch;
    			node[i].num = i;
    		}
    		for (i = 0; i < M; i++)
    		{
        
    			cin >> ch1 >> ch2;
    			for (j = 0; j < N; j++)
    			{
        
    				if (node[j].ch == ch1)
    					a = node[j].num;
    				if (node[j].ch == ch2)
    					b = node[j].num;
    			}
    			cin >> road[a][b];
    			road[b][a] = road[a][b];
    		}
    		cin >> ch1 >> ch2;
    		for (j = 0; j < N; j++)
    		{
        
    			if (node[j].ch == ch1)
    				x = node[j].num;
    			if (node[j].ch == ch2)
    				y = node[j].num;
    		}
    		for (j = 0; j < N; j++)
    		{
        
    			d[j] = x;
    		}
    		DIS(x);
    		if (dis[y] < NNN)
    			cout << dis[y] << endl;
    		else
    			cout << "-1\n";
    		print(y);
    		cout << endl;
    	}
    	return 0;
    }

[http_www.bjfuacm.com]: http://www.bjfuacm.com
[Dijsktra]: https://blog.csdn.net/aaaliaosha/article/details/78458910