top1编程
← 返回题目
题解

【入门】两点之间的最短路径

1 条题解

  • 0
    @ 2026-7-29 0:19:07
    #include<iostream>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int N=105;
    const double INF=1e9;
    struct P{double x,y;}p[N];
    double d[N][N],dis[N];
    bool vis[N];
    int n,m;
    double dist(P a,P b){
        double dx=a.x-b.x;
        double dy=a.y-b.y;
        return sqrt(dx*dx+dy*dy);
    }
    void dijkstra(int s){
        for(int i=1;i<=n;i++){
            dis[i]=INF;
            vis[i]=0;
        }
        dis[s]=0;
        for(int i=1;i<=n;i++){
            int u=0;
            for(int j=1;j<=n;j++){
                if(!vis[j]&&(u==0||dis[j]<dis[u]))u=j;
            }
            vis[u]=1;
            for(int v=1;v<=n;v++){
                if(!vis[v])dis[v]=min(dis[v],dis[u]+d[u][v]);
            }
        }
    }
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++)d[i][j]=INF;
        }
        cin>>m;
        for(int i=1;i<=m;i++){
            int a,b;
            cin>>a>>b;
            d[a][b]=dist(p[a],p[b]);
            d[b][a]=d[a][b];
        }
        int s,t;
        cin>>s>>t;
        dijkstra(s);
        printf("%.2lf",dis[t]);
        return 0;
    }
    
    • 1