最短路径之Floyd算法
Floyd-Warshall算法，简称Floyd算法，用于求解任意两点间的最短距离，时间复杂度为O(n^3)。
输出权值大小及路径：
#include
#include
#include using namespace std;
const int N = 105;
const int INF = 1<<29;int n,m;
int map[N][N];
int dist[N][N];
int path[N][N];void Init()
{for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)map[i][j] = (i == j) ? 0 : INF;
}void Floyd()
{for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){dist[i][j] = map[i][j];path[i][j] = 0;}}for(int k=1; k<=n; k++){for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){if(dist[i][k] + dist[k][j] < dist[i][j]){dist[i][j] = dist[i][k] + dist[k][j];path[i][j] = k;}}}}
}void OutPut(int i,int j)
{if(i == j) return;if(path[i][j] == 0)cout<<"-->"<>n>>m){Init();while(m--){int u,v,w;cin>>u>>v>>w;map[u][v] = w;map[v][u] = w;}int s,t;cin>>s>>t;Floyd();if(dist[s][t] == INF)cout<<"-1"<
题目：http://acm.hdu.edu.cn/showproblem.php?pid=1385
题意：给定一个有向图，每两点之间要么连接，要么不连接，给出所有连接的边的权值，从点a到点b的花费为路径上所有权
值之和加上通过每个点所需要的tax，求a到b的最小花费并输出路径。(如果存在多个最小值，输出经过中间站最少的那个解)。
#include
#include
#include using namespace std;
const int N = 205;
const int INF = 1<<29;int map[N][N];
int path[N][N];
int tax[N];
int n;void Floyd()
{for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)path[i][j] = j;for(int k=1; k<=n; k++){for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){int tmp = map[i][k] + map[k][j] + tax[k];if(tmp < map[i][j]){map[i][j] = tmp;path[i][j] = path[i][k];}else if(tmp == map[i][j] && path[i][j] > path[i][k])path[i][j] = path[i][k];}}}
}void Import()
{for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){cin>>map[i][j];if(map[i][j] == -1)map[i][j] = INF;}}for(int i=1; i<=n; i++)cin>>tax[i];
}int main()
{while(cin>>n){if(n == 0) break;Import();Floyd();while(1){int a,b;cin>>a>>b;if(a==-1 && b==-1) break;cout<<"From"<<" "<"<
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！