题目背景
《爱与愁的故事第三弹·shopping》第一章。
题目描述
中山路店山店海，成了购物狂爱与愁大神的“不归之路”。中山路上有n（n<=100）家店，每家店的坐标均在-10000~10000之间。其中的m家店之间有通路。若有通路，则表示可以从一家店走到另一家店，通路的距离为两点间的直线距离。现在爱与愁大神要找出从一家店到另一家店之间的最短距离。你能帮爱与愁大神算出吗？
输入输出格式
输入格式：
共n+m+3行：
第1行：整数n
第2行~第n+1行：每行两个整数x和y，描述了一家店的坐标
第n+2行：整数m
第n+3行~第n+m+2行：每行描述一条通路，由两个整数i和j组成，表示第i家店和第j家店之间有通路。
第n+m+3行：两个整数s和t，分别表示原点和目标店
输出格式：
仅一行：一个实数（保留两位小数），表示从s到t的最短路径长度。
输入输出样例
输入样例#1：
5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5
输出样例#1：
3.41
说明
100%数据：n<=100，m<=1000
spfa模板题
#include <cstdio>
#include <cmath>
#include <queue> using namespace std;
struct node
{
int next,to;
double dis;
}edge[];
bool vis[];
double dis[];
int tot,i,j,n,m,x[],y[],head[];
inline void add_edge(int u,int v,double farr)
{
edge[++tot].next=head[u];
edge[tot].to=v;
edge[tot].dis=farr;
head[u]=tot;
}
void spfa(int start)
{
queue<int>q;
for(i=;i<=n;++i)
{
dis[i]=1e9;
vis[i]=;
}
dis[start]=;
vis[start]=;
q.push(start);
while(!q.empty())
{
int tope=q.front();
q.pop();
vis[tope]=;
for(i=head[tope];i;i=edge[i].next)
{
int to=edge[i].to;
if(dis[to]>dis[tope]+edge[i].dis)
{
dis[to]=dis[tope]+edge[i].dis;
if(!vis[to])
{
q.push(to);
vis[to]=;
}
}
}
}
}
int main()
{
scanf("%d",&n);
for(i=;i<=n;++i)
scanf("%d%d",&x[i],&y[i]);
int from,to;
scanf("%d",&m);
while(m--)
{
scanf("%d%d",&from,&to);
add_edge(from,to,sqrt((x[from]-x[to])*(x[from]-x[to])+(y[from]-y[to])*(y[from]-y[to])));
add_edge(to,from,sqrt((x[from]-x[to])*(x[from]-x[to])+(y[from]-y[to])*(y[from]-y[to])));
}
int s,t;
scanf("%d%d",&s,&t);
spfa(s);
printf("%.2lf",dis[t]);
return ;
}