floyd，dijkstra
floyd
//最短路径搜索
//floyd算法 算法复杂度n3次方
/*
问题描述：
已知n个点，m条边，求1-n的最短路径
*/
#include<cstdio>
using namespace std;
int mapp[1001][1001];
const int INF=1e6;
int n,m;
int x_init()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j)
{
mapp[i][j]=0;//自己到自己没有距离
}
else
{
mapp[i][j]=INF;
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
x_init;
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
mapp[u][v]=w;
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(mapp[i][k]+mapp[k][j]<mapp[i][j])
{
mapp[i][j]=mapp[i][k]+mapp[k][j];
}
}
}
}
printf("%d\n",mapp[1][n]);//输出
return 0;
}
测试后输出结果有点问题