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

最短路径

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

则从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;
}

?