IT评测·应用市场-qidao123.com

标题: 最短路径问题 [打印本页]

---

作者: 西河刘卡车医    时间: 2023-4-23 21:53
标题: 最短路径问题
平面上有ｎ个点（ｎ＜＝１００），每个点的坐标均在－１００００～１００００之间，其中的一些点之间有连线。
若有连线，则表示可从一个点到达另一个点，即两点间有通路，同路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。
小提示：

• 两点的距离：如果点\(A\)坐标为\((x_A,y_A)\)，点\(B\)的坐标为\((x_B,y_B)\)，\(dis(A,B) = \sqrt{ (x_A-x_B)^2+(y_A-y_B)^2}\)
  C++中求根使用sqrt();
  
• 保留两位小数：使用double变量,double ans;print("%.2lf",ans);
  

输入

共ｎ＋ｍ＋３行。

• 第 1 行：整数ｎ
  
• 第２行到第ｎ＋１行（共ｎ行），每行两个整数ｘ和ｙ，描述一个点的坐标。
  
• 第ｎ＋２行为一个整数ｍ，\(m \leq 1000\)，表示图中连线的个数。
  
• 此后的ｍ行，每行描述一条连线，由两个整数ｉ和ｊ组成，表示第ｉ个点和第ｊ个点之间有连线。
  
• 最后一行：两个整数ｓ和ｔ，分别表示源点和目标点。两个数之间用一个空格隔开。
  

输出

仅一行，一个实数（保留两位小数），表示从ｓ到ｔ的最短路径长度。
样例输入

1. 5
2. 0 0
3. 2 0
4. 2 2
5. 0 2
6. 3 1
7. 5
8. 1 2
9. 1 3
10. 1 4
11. 2 5
12. 3 5
13. 1 5

复制代码

样例输出

1. 3.41

复制代码

1. #include <bits/stdc++.h>
2. using namespace std;
3. int a,b,n,m,vis[10010],x[10010],y[10010];
4. double dis[10010];
5. bool d[1100][1100];
6. queue<int> q;
7. void bfs()
8. {
9.         q.push(a);
10.         dis[a]=0;
11.         vis[a]=1;
12.         while(!q.empty())
13.         {
14.                 int u=q.front();
15.                 q.pop();
16.                 vis[u]=1;
17.                 for(int i=1;i<=b;i++)
18.                 {
19.                         if(d[u][i]&&!vis[i])
20.                         {
21.                                 q.push(i);
22.                                 dis[i]=dis[u]+sqrt(double(x[i]-x[u])*double(x[i]-x[u])+double(y[i]-y[u])*double(y[i]-y[u]));
23.                                 vis[i]=1;
24.                                 if(i==b)
25.                                 {
26.                                         cout << fixed << setprecision(2) << dis[i];
27.                                         return;
28.                                 }
29.                         }
30.                 }
31.         }
32. }
33. int main()
34. {
35.         cin >> n;
36.         for(int i=1;i<=n;i++)
37.         {
38.                 cin >> x[i] >> y[i];
39.         }
40.         cin >> m;
41.         for(int i=1;i<=m;i++)
42.         {
43.                 int f,ff;
44.                 cin >> f >> ff;
45.                 d[f][ff]=d[ff][f]=1;
46.         }
47.         cin >> a >> b;
48.         bfs();
49.         return 0;
50. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

---

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)

Powered by Discuz! X3.4