dijkstra只后面两个点过了
查看原帖
dijkstra只后面两个点过了
194790
祸榊__楼主2020/7/29 11:03

dijkstra只后面两个点过了

//29/07/20 11:00
#include<bits/stdc++.h>
using namespace std;
#define li(i,j,k) for(int i=j ; i<=k ; i++)
#define si(i,j,k) for(int i=j ; i>=k ; i--)
struct yzy{
	int x,y;
}shop[101]; 
int n,m;
int s,t;
double way[101],dis[101][101];
int used[101]={false},v;
double get_dis(int sx,int sy,int ex,int ey){
	return sqrt(pow(sx-ex,2)+pow(sy-ey,2));
}
double min(double a,double b){
	return a<b?a:b;
}
int dijkstra(){
	li(k,1,n){
		v=-1;
		li(i,1,n){
			if(!used[v] && way[i] && (v==-1 || way[i]<way[v])){
				v=i;
			}
		}
		li(i,1,n){
			if(!used[i]){
				way[i]=way[v]+dis[v][i];
				//printf("%d %d\n",i,way[i]);
			}
		}
		used[v]=true;
	}
	return 0;
}
int main(){
	scanf("%d",&n);
	li(i,1,n){
		scanf("%d%d",&shop[i].x,&shop[i].y);
	}
	scanf("%d",&m);
	li(i,1,m){
		int a,b;
		scanf("%d%d",&a,&b);
		dis[a][b]=dis[b][a]=get_dis(shop[a].x,shop[a].y,shop[b].x,shop[b].y);
	}
	scanf("%d%d",&s,&t);
	li(i,1,n){
		if(dis[s][i])way[i]=dis[s][i];
	}
	way[s]=0;
	dijkstra();
	printf("%lf\n",way[t]);
	return 0;
}
2020/7/29 11:03
加载中...