本文主要是介绍数据结构-怀化学院期末题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最短路径
描述：
已知一个城市的交通路线，经常要求从某一点出发到各地方的最短路径。例如有如下交通图：
则从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;
}
这篇关于数据结构-怀化学院期末题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
