首頁/ 文章/ c++SPFAsu

c++SPFAsu

2025-02-21 21:58  瀏覽數:246  來源:Xu Pair    

#include<bits/stdc++.h>
using namespace std;
int a[1005][3],f[1005][3],n,m,s,e;
double w[1005],d[1005];
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i][0]>>a[i][1];
cin>>m;
for(int i=1;i<=n;i++)d[i]=f[i][1]=f[i][2]=0x7fffffff/3;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
f[i][1]=x;
f[i][2]=y;
w[i]=sqrt(pow(double(a[x][0]-a[y][0]),2)+pow(double(a[x][1]-a[y][1]),2));
}
cin>>s>>e;
d[s]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(d[f[j][1]]+w[j]<d[f[j][2]]) d[f[j][2]]=d[f[j][1]]+w[j];
if(d[f[j][2]]+w[j]<d[f[j][1]]) d[f[j][1]]=d[f[j][2]]+w[j];
}
}
printf("%.2f\n",d[e]);
return 0;
}



聲明:以上文章均為用戶自行添加,僅供打字交流使用,不代表本站觀點,本站不承擔任何法律責任,特此聲明!如果有侵犯到您的權利,請及時聯系我們刪除。

字符:    改为:
去打字就可以设置个性皮肤啦!(O ^ ~ ^ O)