提交时间:2022-06-12 07:06:29

运行 ID: 41440

#include <bits/stdc++.h> using namespace std; struct Point{int x,y;}; int main() { int n; cin>>n; vector<Point>p(n+1); for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y; int m; cin>>m; const int M=10000*10; vector<vector<double> >d(n+1,vector<double>(n+1,M)); for(int i=1;i<=m;i++) { int a, b; cin>>a>>b; double dx=p[a].x-p[b].x; double dy=p[a].y-p[b].y; double dd=sqrt(dx*dx+dy*dy); d[a][b]=d[b][a]=dd; } 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) continue; double dd=d[i][k]+d[k][j]; d[i][j]=min(d[i][j], dd); } } } int s,t; cin>>s>>t; cout<<fixed<<setprecision(2)<<d[s][t]; return 0; }