本文共 858 字，大约阅读时间需要 2 分钟。

这里用迪杰斯特拉

#include 
   
    #include 
    
     #include 
     
      using namespace std;int main(){
   	double e[100][100];	int n,m,p[100][100],q1,q2,book[100]={
   0},u,start,end;	double mini,maxn=99999.00;	cin>>n;	for(int i=1;i<=n;i++)		for(int j=1;j<=n;j++)			if(i==j)				e[i][j]=0;			else				e[i][j]=maxn;	for(int i=1;i<=n;i++)		cin>>p[i][1]>>p[i][2];	cin>>m;	for(int i=1;i<=m;i++){
   		cin>>q1>>q2;		e[q1][q2]=sqrt(pow(p[q1][1]-p[q2][1],2)+pow(p[q1][2]-p[q2][2],2));		e[q2][q1]=e[q1][q2];	}	cin>>start>>end;	for(int i=1;i<=n;i++)		e[start][i]=e[1][i];	book[1]=0;	for(int i=1;i<=n;i++){
   		mini=maxn;		for(int j=1;j<=n;j++){
   			if(book[j]==0&&mini>e[start][j]){
   				u=j;				mini=e[start][j];			}		}		book[u]=1;		for(int k=1;k<=m;k++)			if(e[start][k]>e[start][u]+e[u][k])				e[start][k]=e[start][u]+e[u][k];	}	printf("%.2f",e[start][end]);	return 0;}
     
    
   

转载地址：http://luggf.baihongyu.com/