根据样例画图为上. 求dis[1][5]
#include<cstdio> #include<cmath> #include<iostream> #include<cstring> using namespace std; int a[101][3]; double f[101][101]; //floyed存储了 任意2点间最短路 int n,i,j,k,x,y,m,s,e; int main() { //存到同一目录下面用文件的方式读入 freopen("short.in","r",stdin); freopen("short.out","w",stdout); cin>>n; for(i=1;i<=n;i++) cin>>a[i][1]>>a[i][2]; cin>>m; memset(f,0x7f,sizeof(f)); for(i=1;i<=m;i++) { cin>>x>>y; f[y][x]=f[x][y]=sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2)); } cin>>s>>e; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if((f[i][j]>f[i][k]+f[k][j])&&(i!=j)&&(i!=k)&&(j!=k)) f[i][j]=f[i][k]+f[k][j]; printf("%.2lf ",f[s][e]); return 0; }
（1）算法分析：//使用floyed之前，f[][] 中存储情况
#include<cstdio> #include<cmath> #include<iostream> #include<cstring> using namespace std; int a[101][3]; double f[101][101]; //floyed存储了 任意2点间最短路 int n,i,j,k,x,y,m,s,e; int main() { //存到同一目录下面用文件的方式读入 freopen("short.in","r",stdin); freopen("short.out","w",stdout); cin>>n; for(i=1;i<=n;i++) cin>>a[i][1]>>a[i][2]; cin>>m; memset(f,0x7ffffff,sizeof(f)); for(i=1;i<=m;i++) { cin>>x>>y; f[y][x]=f[x][y]=sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2)); } //使用floyed之前，f[][] 中存储情况 for(int i=1;i<=m;i++) { for(int j=1;j<=m;j++) { printf("%.2lf ",f[i][j]); } cout<<" "; } return 0; }
各个节点间距离情况， nan表示无直接连通。
（2）输出floyed表中全部【各个节点间距离情况】//跑完一遍floyed之后的 f[][]情况
#include<cstdio> #include<cmath> #include<iostream> #include<cstring> using namespace std; int a[101][3]; double f[101][101]; //floyed存储了 任意2点间最短路 int n,i,j,k,x,y,m,s,e; int main() { //存到同一目录下面用文件的方式读入 freopen("short.in","r",stdin); freopen("short.out","w",stdout); cin>>n; for(i=1;i<=n;i++) cin>>a[i][1]>>a[i][2]; cin>>m; memset(f,0x7f,sizeof(f)); for(i=1;i<=m;i++) { cin>>x>>y; f[y][x]=f[x][y]=sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2)); } //跑一边floyed。 for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if((f[i][j]>f[i][k]+f[k][j])&&(i!=j)&&(i!=k)&&(j!=k)) f[i][j]=f[i][k]+f[k][j]; //使用floyed之后，f[][] 中存储情况 【便于分析查看】 for(int i=1;i<=m;i++) { for(int j=1;j<=m;j++) { printf("%.2lf ",f[i][j]); } cout<<" "; } return 0; }
上表中 很详细的记录了，各个点之间的最短路径，floyed很强大的！！！
其它说明：以上程序用到freopen() 所以，各个文件要在同一个目录之中。