Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
41440 | 杨中琦 | 最短路径问题 | C++ | 通过 | 100 | 4 MS | 344 KB | 875 | 2022-06-12 07:06:29 |
#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; }