这道题是最短路呀,用dijskra呀
by xfx2011 @ 2024-02-13 15:56:31
或者floyd
by xfx2011 @ 2024-02-13 15:56:58
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100 + 10;
double x[maxn],y[maxn];
double dp[maxn][maxn];
int m,n;
void floyd(){
for(int k = 1;k <= n;k ++){
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= n;j ++){
dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j]);
}
}
}
}
int main(){
// freopen("cai.in","r",stdin);
// freopen("cai.out","w",stdout);
cin >> n;
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= n;j ++)
dp[i][j] = 0x3f3f3f3f;
dp[i][i] = 0;
}
for(int i = 1;i <= n;i ++)
cin >> x[i] >> y[i];
cin >> m;
for(int i = 1;i <= m;i ++){
int u,v;
cin >> u >> v;
double dist = sqrt(((x[u] - x[v])) * ((x[u] - x[v])) + ((y[u] - y[v])) * ((y[u] - y[v]))) * 1.00;
dp[u][v] = dist;
dp[v][u] = dist;
}
floyd();
int s,t;
cin >> s >> t;
printf("%.2lf",dp[s][t]);
return 0;
}
```
by xfx2011 @ 2024-02-13 16:01:11
谢谢dalao,已关
by Even_If @ 2024-02-13 16:01:50