@[SGOI_BGlove](/space/show?uid=39850) 你用markdown 不行吗?
by Xxzxx @ 2018-10-15 18:54:06
```cpp
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
int n,m;
int s,t;
struct jg{
int x;
int y;
};
jg dzb[109];
vector<int> tt[109];
queue <int> pp;
double d[109];
int bj[109];
double js(int a,int b){
return sqrt((double)(dzb[a].x-dzb[b].x)*(dzb[a].x-dzb[b].x)+(double)(dzb[a].y-dzb[b].y)*(dzb[a].y-dzb[b].y));
}
void spfa(int a){
pp.push(a);
while(!pp.empty()){
int tmp=pp.front();
pp.pop();
bj[a]=0;
//cout<<tmp<<" "<<dzb[tmp].x<<" "<<dzb[tmp].y<<" "<<d[tmp]<<endl;
for(int i=0;i<tt[tmp].size();i++){
if(d[tt[tmp][i]]>(js(tt[tmp][i],tmp)+d[tmp])){
d[tt[tmp][i]]=js(tt[tmp][i],tmp)+d[tmp];
if(bj[tt[tmp][i]]==0){
pp.push(tt[tmp][i]);
bj[tt[tmp][i]]=1;
}
}
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>dzb[i].x>>dzb[i].y;
}
cin>>m;
for(int i=1;i<=n;i++){
int a,b;
cin>>a>>b;
tt[a].push_back(b);
tt[b].push_back(a);
}
cin>>s>>t;
for(int i=1;i<109;i++){
d[i]=9999999999.0;
}
d[s]=0.0;
spfa(s);
printf("%.2lf",d[t]);
return 0;
}
```
by SGOI_BGlove @ 2018-10-15 18:58:33