Floyd模板(详细操作最基础版)
#include<cstdio>
#include<iostream>
using namespace std;
#define MAX 500
#define INFE 1<<20
int N;
int map[MAX][MAX],b[MAX],path[MAX][MAX]; //path[i][j]记录路径
void init()
{
int i,j;
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
{
map[i][j]=INFE;
path[i][j]=j;
}
}
void floyd()
{
int i,j,k;
for(k=1;k<=N;k++)
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
if(map[i][j]>map[i][k]+map[k][j])
{
map[i][j]=map[i][k]+map[k][j];
path[i][j]=path[i][k];
}
}
int main()
{
int m,u,v,len;
while(scanf("%d%d",&N,&m)!=EOF) //输入城市数量 和 道路数量
{
init();//初始化
while(m--)
{
scanf("%d%d%d",&u,&v,&len);
map[u][v]=map[v][u]=len;
}
floyd();//进行每对节点的求最小路径
while(scanf("%d%d",&u,&v))
{//输入起点和终点
int tmp=u;
printf("%d",u);
while(tmp!=v)
{//打印路径
printf("-->%d",path[tmp][v]);
tmp=path[tmp][v];
}
//输出最小花费
cout<<endl;
cout<<"cost: "<<map[u][v]<<endl;
}
}
return 0;
}
版权声明:本文为博主原创文章,未经博主允许不得转载。
posted on
2014-07-19 11:21
france 阅读(
...) 评论(
...)
编辑
收藏