subject

• Description

There are n points (n < = 100) in the plane, and the coordinates of each point are between - 10000 and 10000. There is a line between some of these points. If there is a line, it means that there is a path from one point to another, that is, there is a path between two points, and the distance of the path is the distance between two straight lines. The task now is to find the shortest path from one point to another.

• Input

The input file short.in has n+m+3 lines, where:
The first line is an integer n.
Line 2 to line n+1 of N, two integers x and y in each line, describing the coordinates of a point (separated by a space).
The n+2 is an integer m, indicating the number of lines in the graph.
In the following m lines, each line describes a line, which is composed of two integers i and j, indicating that there is a line between the I point and the J point.
The last line: two integers, s and t, represent the source point and the target point respectively.

• Output

The output file, short.out, has only one line, a real number (two decimal places reserved), representing the length of the shortest path from S to T.

• Sample Input
  5
  0 0
  2 0
  2 2
  0 2
  3 1
  5
  1 2
  1 3
  1 4
  2 5
  3 5
  1 5

• Sample Output
  3.41

Solutions to problems

**>This is a shortest path problem.

Code (1) [Floyd]

#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std; 
int a[101][3];
double f[101][101]; 
int n,i,j,k,x,y,m,s,e;
int main()
{
    scanf("%d",&n); 
    for (int i=1;i<=n;i++)
     scanf("%d%d",&a[i][1],&a[i][2]); 
    scanf("%d",&m); 
    memset(f,0x7f,sizeof(f));
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&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));
    }//Pretreatment
    scanf("%d%d",&s,&e); 
    for (k=1;k<=n;k++)
     for (i=1;i<=n;i++)
      for (j=1;j<=n;j++)
       if ((i!=j)&&(i!=k)&&(j!=k)&&(f[i][k]+f[k][j]<f[i][j]))
        f[i][j]=f[i][k]+f[k][j]; 
    printf("%.2lf\n",f[s][e]); //Notice it's a decimal
    return 0; 
}

Code (2) [Dijkstra]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std; 
int a[101][3];
double c[101],f[101][101];
bool b[101]; 
int n,i,j,k,x,y,m,s,e; 
double minl; 
double maxx=1e30; 
int main()
{
    scanf("%d",&n); 
    for (i=1;i<=n;i++)
     cin>>a[i][1]>>a[i][2]; 
    for (i=1;i<=n;i++)
     for (j=1;j<=n;j++)
      f[i][j]=maxx; 
    cin>>m; 
    for (i=1;i<=m;i++)
     {
        cin>>x>>y; 
        f[x][y]=f[y][x]=sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2));
     }//Pretreatment
    cin>>s>>e; 
    for (i=1;i<=n;i++)
     c[i]=f[s][i]; 
    memset(b,false,sizeof(b)); 
    b[s]=true; 
    c[s]=0; 
    for (i=1;i<=n-1;i++)
    {
        minl=maxx; 
        k=0; 
        for (j=1;j<=n;j++)
         if ((!b[j])&&(c[j]<minl))
         {
            minl=c[j]; //Record the minimum value each time
            k=j; //Record the smallest node
         }
        if (k==0) break; //The current node has no surrounding nodes
        b[k]=true; //Put new nodes into a set
        for (j=1;j<=n;j++)
         if (c[k]+f[k][j]<c[j]) c[j]=c[k]+f[k][j];//When a new point is added, update the distance between the current shortest path set and other points
    }
    printf("%.2lf\n",c[e]); 
    return 0; 
}