平面上有ｎ個點（ｎ＜＝１００），每個點的坐標均在－１００００～１００００之間，其中的一些點之間有連線。 若有連線，則表示可從一個點到達另一個點，即兩點間有通路，同路的距離為兩點間的直線距離。現在的任務是找出從一點到另一點之間的最短路徑。 小提示： 兩點的距離：如果點$A$坐標為$(x_A,y_A)$ ...
平面上有ｎ個點（ｎ＜＝１００），每個點的坐標均在－１００００～１００００之間，其中的一些點之間有連線。
若有連線，則表示可從一個點到達另一個點，即兩點間有通路，同路的距離為兩點間的直線距離。現在的任務是找出從一點到另一點之間的最短路徑。
小提示：
- 兩點的距離：如果點\(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\)，表示圖中連線的個數。
-
此後的ｍ行，每行描述一條連線，由兩個整數ｉ和ｊ組成，表示第ｉ個點和第ｊ個點之間有連線。
-
最後一行：兩個整數ｓ和ｔ，分別表示源點和目標點。兩個數之間用一個空格隔開。
輸出
僅一行，一個實數（保留兩位小數），表示從ｓ到ｔ的最短路徑長度。
樣例輸入
5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5
樣例輸出
3.41
#include <bits/stdc++.h>
using namespace std;
int a,b,n,m,vis[10010],x[10010],y[10010];
double dis[10010];
bool d[1100][1100];
queue<int> q;
void bfs()
{
q.push(a);
dis[a]=0;
vis[a]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=1;
for(int i=1;i<=b;i++)
{
if(d[u][i]&&!vis[i])
{
q.push(i);
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]));
vis[i]=1;
if(i==b)
{
cout << fixed << setprecision(2) << dis[i];
return;
}
}
}
}
}
int main()
{
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> x[i] >> y[i];
}
cin >> m;
for(int i=1;i<=m;i++)
{
int f,ff;
cin >> f >> ff;
d[f][ff]=d[ff][f]=1;
}
cin >> a >> b;
bfs();
return 0;
}
本文來自小默的博客，轉載請註明原文鏈接：https://www.cnblogs.com/momotrace/p/shortest-road_pr.html
