題目連結:
https://www.luogu.org/problemnew/show/P1744
思路:
1:裸的最短路
2:spfa算法
#include <bits/stdc++.h>
using namespace std;
const int maxn=101;
vector<pair<int,double> >e[maxn];
int n,m,x,y,a,b,s,t;
vector<pair<int,int> >vec;
double d[maxn];
int ing[maxn];
inline void init()
{
for(int i=1;i<=n;i++)
{
d[i]=DBL_MAX;
}
}
int main()
{
cin>>n;
init();
for(int i=0;i<n;i++)
{
cin>>x>>y;
vec.push_back(make_pair(x,y));
}
cin>>m;
for(int i=0;i<m;i++)
{
cin>>a>>b;
double dis=sqrt(pow(vec[a-1].first-vec[b-1].first,2)+pow(vec[a-1].second-vec[b-1].second,2));
e[a].push_back(make_pair(b,dis));
e[b].push_back(make_pair(a,dis));
}
cin>>s>>t;
queue<int>q;
q.push(s);
d[s]=0;
ing[s]=1;
while(!q.empty())
{
int now=q.front();
q.pop();
ing[now]=0;
for(int i=0;i<e[now].size();i++)
{
int v=e[now][i].first;
if(d[v]>d[now]+e[now][i].second)
{
d[v]=d[now]+e[now][i].second;
if(ing[v])continue;
q.push(v);
}
}
}
cout<<fixed<<setprecision(2)<<d[t]<<endl;
return 0;
}