题解
【入门】两点之间的最短路径
1 条题解
-
0
#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