最短路径
描述：
已知一个城市的交通路线，经常要求从某一点出发到各地方的最短路径。例如有如下交通图：
则从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;
}
