题目描述 Description平面上有n个点(n<=100),每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。
输入描述 Input Description第一行为整数n。
第2行到第n+1行(共n行),每行两个整数x和y,描述了一个点的坐标。
第n+2行为一个整数m,表示图中连线的个数。
此后的m行,每行描述一条连线,由两个整数i和j组成,表示第i个点和第j个点之间有连线。
最后一行:两个整数s和t,分别表示源点和目标点。
输出描述 Output Description仅一行,一个实数(保留两位小数),表示从s到t的最短路径长度。
样例输入 Sample Input5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5
样例输出 Sample Output3.41
数据范围及提示 Data Size & Hint。
连边,然后跑SPFA
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> #include<vector> #include<map> #include<set> #include<queue> #include<string> #define inf 1000000000000ll #define maxn 500000+5 #define maxm 8000000+5 #define eps 1e-10 #define ll long long #define pa pair<int,int> #define for0(i,n) for(int i=0;i<=(n);i++) #define for1(i,n) for(int i=1;i<=(n);i++) #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go) #define mod 1000000007 #define lch t[k].l,l,mid #define rch t[k].r,mid+1,r using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();} return x*f; } int n,head[maxn],mx=1000000,tot,a[maxn],m;//n double d[maxn]; bool v[maxn]; queue<int>q; struct edge{int go,next;double w;}e[maxm]; struct point{int x,y; }points[110]; inline void add(int x,int y,double w) { e[++tot]=(edge){y,head[x],w}; head[x]=tot; } int main() { n=read(); for1(i,n){ int x=read(),y=read(); points[i]=(point){x,y} ; } m=read(); for1(i,m){ int y=read(),dd=read(); add(y,dd,sqrt((points[y].x-points[dd].x)*(points[y].x-points[dd].x)+(points[y].y-points[dd].y)*(points[y].y-points[dd].y))); add(dd,y,sqrt((points[y].x-points[dd].x)*(points[y].x-points[dd].x)+(points[y].y-points[dd].y)*(points[y].y-points[dd].y))); } for1(i,n)d[i]=inf; int s=read(),t=read(); d[s]=0;q.push(s); while(!q.empty()) { int x=q.front();q.pop();v[x]=0; for4(i,x)if(d[x]+e[i].w<d[y]) { d[y]=d[x]+e[i].w; if(!v[y]){v[y]=1;q.push(y);} } } printf("%0.2f",d[t]); return 0; }