1 条题解
-
0
对欧氏边长做Floyd,正确处理同点查询、重边和重合坐标。
#include <bits/stdc++.h> using namespace std; int main(){ios::sync_with_stdio(false);cin.tie(nullptr); int n;cin>>n;vector<pair<int,int>>a(n);for(auto&[x,y]:a)cin>>x>>y;const long double INF=numeric_limits<long double>::infinity();vector<vector<long double>>d(n,vector<long double>(n,INF));for(int i=0;i<n;i++)d[i][i]=0;int m;cin>>m;while(m--){int u,v;cin>>u>>v;--u;--v;d[u][v]=d[v][u]=hypotl((long double)a[u].first-a[v].first,(long double)a[u].second-a[v].second);}for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);int s,t;cin>>s>>t;cout<<fixed<<setprecision(2)<<d[s-1][t-1]<<"\n"; return 0; }
- 1
信息
- ID
- 4017
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 5
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者