数据结构-怀化学院期末题

2024-01-08 23:07:57

最短路径

描述:
已知一个城市的交通路线,经常要求从某一点出发到各地方的最短路径。例如有如下交通图:

则从A出发到各点的最短路径分别为:
B:0
C:10
D:50
E:30
F:60
输入:
输入只有一个用例,第一行包括若干个字符,分别表示各顶点的名称,接下来是一个非负的整数方阵,方阵维数等于顶点数,其中0表示没有路,正整数表示两点之间边的长度。可以假定该图为有向图。
最后一行为要求的出发点。
输出:
输出从已知起点到各顶点的最短路径长度。输出格式是根据顶点输入顺序,依次输出其最智短路径长度。各顶点分别用一行输出,先输出目标顶点,然后一冒号加一个空格,最后是路径长度。0表示没有路。

输入样例:

ABCDEF
0 0 10 0 30 100
0 0 5 0 0 0
0 0 0 50 0 0
0 0 0 0 0 10
0 0 0 20 0 60
0 0 0 0 0 0
A?

输出样例:

?B: 0
C: 10
D: 50
E: 30
F: 60

本题使用Floyd算法 O(n^3)动态规划

代码:

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;
map<char,int> mp;
string str;
int a[N][N];
void floyd(){
	for(int k = 0;k < str.length();k ++){
		for(int i = 0;i < str.length();i ++){
			for(int j = 0;j < str.length();j ++){
				a[i][j] = min(a[i][j],a[i][k]+a[k][j]);
			}
		}			
	}
}
int main(){
	
	cin >> str;
	for(int i = 0;i < str.size();i ++){
		mp[str[i]] = i;
	}
	int x;
	for(int i = 0;i < str.length();i ++){
		for(int j = 0;j < str.length();j ++){
			cin >> a[i][j];
			if(a[i][j] == 0)
				a[i][j] = INF;
		}
	}
	floyd();
	char q;
	cin >> q;
	for(int i = 0;i < str.length();i ++){
		if(str[i] != q){
			cout << str[i] << ": " ;
			if(a[mp[q]][mp[str[i]]] > INF/2) cout << "0" << endl;
			else cout << a[mp[q]][mp[str[i]]] << endl;
		}
	}
	return 0;
}

?

文章来源:https://blog.csdn.net/weixin_72982195/article/details/135467060
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。