题目

一个图，求两个点的最短路径

输入

第一行为一个整数n。

n行，两个整数x和y，一个点的坐标

一个整数m，表示图中线的个数。

m行，一条线，i,j，表示第i个点和第j个点之间有线。

最后一行：两个整数s和t，分别表示源点和目标点。

5

0 0

2 0

2 2

0 2

3 1

5

1 2

1 3

1 4

2 5

3 5

1 5

输出

最短路（保留两位小数）

3.41

---

解题思路

沟谷求路径长度，然后最短路，这里用O(n^3)的方法（Floyd法）

---

代码

#include
    
     #include
     
      #include
      
       using namespace std;int n,dxx,dyy,m;int xx[101],yy[101];double a[101][101];int main(){    scanf("%d",&n);    for (int i=1;i<=n;i++)    {        scanf("%d%d",&xx[i],&yy[i]);//输入    }    for (int i=1;i<=n;i++)      for (int j=1;j<=n;j++) a[i][j]=233333333;      //初始化    scanf("%d",&m);    for (int i=1;i<=m;i++)    {        scanf("%d%d",&dxx,&dyy);        a[dxx][dyy]=sqrt(abs(xx[dxx]-xx[dyy])*abs(xx[dxx]-xx[dyy])+abs(yy[dxx]-yy[dyy])*abs(yy[dxx]-yy[dyy]));        a[dyy][dxx]=sqrt(abs(xx[dxx]-xx[dyy])*abs(xx[dxx]-xx[dyy])+abs(yy[dxx]-yy[dyy])*abs(yy[dxx]-yy[dyy]));        //求距离（沟谷）    }    scanf("%d%d",&dxx,&dyy);//点    for (int k=1;k<=n;k++)//枚举一个中点      for (int i=1;i<=n;i++)        for(int j=1;j<=n;j++)          a[i][j]=min(a[i][j],a[i][k]+a[k][j]);           //经过中点k从i到j      printf("%.2lf",a[dxx][dyy]);//输出}