【codevs2602】最短路径问题

problem

solution

codes

#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

int a[101],b[101];
double f[101][101];
int n,m,x,y,s,t;

void floyd(){
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
          for(int 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];
}
void read(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d%d",&a[i],&b[i]);
    scanf("%d",&m);
    memset(f,0x7f,sizeof(f));
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        f[x][y]=f[y][x]=sqrt(pow(double(a[x]-a[y]),2)+pow(double(b[x]-b[y]),2));
    }
    scanf("%d%d",&s,&t);
}
int main(){
    read();
    floyd();        
    printf("%.2lf",f[s][t]);
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80554844