文章
10
粉丝
179
获赞
5
访问
31.1k
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1e9;
int n,m,S,T,A;
int mp[1001][1001];//存储图像
string path[1001][1001]; //以字符串的方式记录每个点之间的最佳路径
string name[1001];//记录顶点
void floyd(){ //弗洛伊德函数
for(int i=1;i<=n;i++){ //初始化path路径数组
//path[i]=new string [n];
for(int j=1;j<=n;j++){
if(i==j) path[i][j]=name[i];
else path[i][j]=name[i]+name[j];
}
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(mp[i][k]==INF || mp[k][j]==INF) continue;
if(i!=j){
if(mp[i][j]==INF || mp[i][j]>mp[i][k]+mp[k][j]){
mp[i][j]=mp[i][k]+mp[k][j]; //计算单源最短路径
path[i][j]=path[i][k].substr(0,path[i][k].length()-1)+path[k][j]; //若i通过k到j的距离更短,则将i到k的路径的字符串与k到j的路径合并到一起,因为k是重复的,所以要减去一个k
...
登录后发布评论
暂无评论,来抢沙发