当前位置:   article > 正文

BJFU_数据结构习题_273基于Dijsktra算法的最短路径求解_输入要求: 两组数据,每组数据有m+3行。第一行为两个整数n和m,分别代表城市个数n和

输入要求: 两组数据,每组数据有m+3行。第一行为两个整数n和m,分别代表城市个数n和

欢迎登录北京林业大学OJ系统
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算法的最短路径求解

#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
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/711009
推荐阅读
相关标签
  

闽ICP备14008679号