采购特价商品

题目背景

《爱与愁的故事第三弹·shopping》第一章。

题目描述

中山路店山店海，成了购物狂爱与愁大神的“不归之路”。中山路上有 $n$ （ $n \leq 100$ ）家店，每家店的坐标均在 $-10000$ 至 $10000$ 之间。其中的 $m$ 家店之间有通路。若有通路，则表示可以从一家店走到另一家店，通路的距离为两点间的直线距离。现在爱与愁大神要找出从一家店到另一家店之间的最短距离。你能帮爱与愁大神算出吗？

输入格式

共 $n+m+3$ 行：

第一行：整数 $n$ 。

接下来 $n$ 行：每行两个整数 $x$ 和 $y$ ，描述了一家店的坐标。

接下来一行：整数 $m$ 。

接下来 $m$ 行：每行描述一条通路，由两个整数 $i$ 和 $j$ 组成，表示第 $i$ 家店和第 $j$ 家店之间有通路。

接下来一行：两个整数 $s$ 和 $t$ ，分别表示原点和目标店。

输出格式

仅一行：一个实数（保留两位小数），表示从 $s$ 到 $t$ 的最短路径长度。

样例 #1

样例输入 #1

样例输出 #1

3.41

提示

对于 $100 \%$ 的数据： $2 \le n \leq 100$ ， $1 \le i, j, s, t \le n$ ， $1 \le m \leq 1000$ 。

#include<bits/stdc++.h>
using namespace std;
int head[10099],k=0,x[10086],y[10086],n,m,s,t,u,v;
bool vis[10086];
double d[10086];
struct aaaa{
	int next,to;
	double w;
}e[100008];
double dis(int x2,int xx,int y2,int yy){
	double z=(x2-xx)*(x2-xx);
	double zz=(y2-yy)*(y2-yy);
	double zzz=sqrt(z+zz);
	return zzz;
}
void adddd(int u,int v,double w){
	k++;
	e[k].next=head[u];
	e[k].to=v;
	e[k].w=w;
	head[u]=k;
}
void spfa(){
	queue<int> q;
	d[s]=0;
	vis[s]=1;
	q.push(s);
	
	while(!q.empty()){
		int fa=q.front();
		q.pop();
		for(int i=head[fa];i;i=e[i].next){
			int v=e[i].to;
			double huan=d[fa]+e[i].w;
			if(huan<d[v]){
				d[v]=huan;
				if(vis[v]==0){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
}
int main(){
	memset(head,-1,sizeof(head));
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>x[i]>>y[i];
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		double wi=dis(x[u],x[v],y[u],y[v]);
		adddd(u,v,wi);
		adddd(v,u,wi);
	}
	cin>>s>>t;
	for(int i=1;i<=n;i++) d[i]=1000000000;
	spfa();
	printf("%.2lf",d[t]);
}
/*
5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5


大样例
50
5348 -9992
9623 9946
-8630 5234
-8233 -7005
-518 6249
-119 -7433
-8602 -8651
9054 -2844
9815 -9938
2167 -7594
-5825 -9257
-8357 8644
-7907 6406
-7674 3970
8592 9700
139 -3629
372 -7003
-3745 3261
7288 -5491
1424 -8098
-1787 -3628
-9826 9151
-6509 5650
-440 3947
-8845 -5820
-7851 998
9105 -1789
-2063 9101
423 3750
4869 -7489
4037 8582
-7330 -1161
-2116 -3115
9662 1867
6794 7374
-2751 2759
2264 925
-8224 -1920
-3688 -1397
-1564 8071
-3395 6046
-3097 3616
-4957 5121
3414 -4661
6982 -1182
-1057 -6736
3294 292
-1813 -9520
2452 2009
-962 9250
100
13 40
19 8
16 27
15 7
10 17
36 27
46 11
43 2
6 49
38 49
48 15
31 29
1 30
49 5
35 14
41 8
17 10
43 48
26 8
16 26
49 18
10 28
11 11
40 18
27 1
44 6
24 12
37 42
23 30
16 6
19 1
42 37
20 16
27 17
49 4
50 30
21 49
29 24
42 43
50 28
29 48
33 35
40 9
25 5
12 26
45 2
35 42
43 25
35 26
23 26
11 42
17 8
37 13
22 7
35 30
45 39
13 46
6 34
4 38
35 13
4 49
49 11
47 4
47 22
29 10
5 34
28 39
21 35
34 41
15 48
49 8
30 19
34 5
34 48
12 26
14 44
11 5
38 26
33 19
36 36
17 42
15 49
1 4
26 19
26 42
28 36
5 31
41 43
45 39
5 21
50 39
14 11
24 31
16 10
34 37
26 38
17 3
15 24
24 38
2 3
2 7
输出
71722.64
我的输出
77353.54
只wa这一个点
*/

帮帮我万能的谷民们QAQAQAQAQAQAQ

2024/7/30 21:26