18732 最短路问题

迷南。 2023-02-14 10:40 9阅读 0赞

时间限制:1000MS 代码长度限制:10KB  
提交次数:0 通过次数:0

题型: 编程题 语言: 不限定  
Description  
现在有n个车站和m条直达公交线路，每条线路都有一个固定票价。  
作为一个窮人，你打算从车站1坐车到车站n，请计算下车站1到车站n的最少花费。  
如果车站1无法到达车站n，请输出-1。  
注意，在车站x和y之间可能存在不止一条线路。

输入格式  
第一行两个整数n和m，表示车站数量和线路数量。(1<=n<=100),(1<=m<=1000)  
第二行至第m+1行，每行3个整数a,b,x，代表车站a和车站b之间有一条票价为x的公交线路，公交线路是双向的。

输出格式  
输出车站1到n的最小花费。

输入样例  
4 4  
1 2 4  
2 3 7  
2 4 1  
3 4 6

输出样例  
5

作者 30002692

解题思路一：由于数据量较小，可以考虑弗洛伊德算法。

#include<iostream>
    #include<cstring> 
    using namespace std;
    int a[105][105];
    int main()
    { 
    	int x,y,z,i,n,m,j,k;
    	ios::sync_with_stdio(false);
    	memset(a,127/3,sizeof(a));//初始化距离未无穷大 
    	cin>>n>>m;
    	for(i=1;i<=n;i++)//自身到自身的距离为0 
    	a[i][i]=0;
    	for(i=1;i<=m;i++)
    	{ 
    		cin>>x>>y>>z;
    		a[x][y]=a[y][x]=z;//此题为无向网 
    	}
    	for(k=1;k<=n;k++)//弗洛伊德算法核心 
    	for(i=1;i<=n;i++)
    	for(j=1;j<=n;j++)
    	if(a[i][k]+a[k][j]<a[i][j])
    	a[i][j]=a[i][k]+a[k][j];
    	if(a[1][n]>999999)
    	cout<<-1;
    	else 
    	cout<<a[1][n];
    	return 0;
    }

打印路径版：

#include<iostream>
    #include<cstring> 
    using namespace std;
    int a[105][105];
    int path[105][105];//path[i][j]=x表示从顶点i到顶点j的路径中j的前驱为x 
    int s[1000],top=0; 
    int main()
    { 
    	int x,y,z,i,n,m,j,k;
    	ios::sync_with_stdio(false);
    	memset(a,127/3,sizeof(a));//初始化距离未无穷大 
    	cin>>n>>m;
    	for(i=1;i<=n;i++)//自身到自身的距离为0 
    	a[i][i]=0;
    	for(i=1;i<=m;i++)
    	{ 
    		cin>>x>>y>>z;
    		a[x][y]=a[y][x]=z;//此题为无向网 
    		path[x][y]=x;
    		path[y][x]=y;
    	}
    	for(k=1;k<=n;k++)//弗洛伊德算法核心 
    	for(i=1;i<=n;i++)
    	for(j=1;j<=n;j++)
    	if(a[i][k]+a[k][j]<a[i][j])
    	{ 
    		a[i][j]=a[i][k]+a[k][j];
    		path[i][j]=path[k][j];
    	}
    	int temp=path[1][n];//路径转换 
    	s[top++]=temp; 
    	while(path[1][temp]!=1)
    	{ 
    		temp=path[1][temp];
    		s[top++]=temp;
    	}
    	if(a[1][n]>999999)
    	cout<<-1;
    	else 
    	cout<<a[1][n];
    	cout<<endl;
    	cout<<1<<' ';//打印1到n的最短路径 
    	while(top)
    	{ 
    		cout<<s[--top]<<' ';
    	}
    	cout<<n<<' ';
    	return 0;
    }

此外还可以使用单源点的迪杰斯特拉算法。

#include<iostream>//迪杰斯特拉算法求最短路径 （无向网） 
    #include<cstring>
    using namespace std;
    int a[105][105],d[105],v[105],path[105],n,m;
    //数组a存储边和权值，数组d存储从某个源点start到i的最短路径，数组v记录i是否被用来刷新过数组d，path记录路径
    int GetMin()//获取start和i之间最小权值且未被访问过的点的下标 
    { 
    	int minv=1e9,mini,i;
    	for(i=1;i<=n;i++)
    	{ 
    		if(v[i]==0&&d[i]<minv)
    		minv=d[i],mini=i;
    	}
    	return mini;
     } 
     void djstra(int start)
     { 
     	int i,j;
     	v[start]=1;
     	for(i=1;i<=n;i++)
     	d[i]=a[start][i];
     	for(i=1;i<n;i++)
     	{ 
     		int u=GetMin();//获取最佳的u来刷新 
     		v[u]=1;
     		for(j=1;j<=n;j++)
     		if(d[j]>d[u]+a[u][j])
    		d[j]=d[u]+a[u][j];
    	 }
     }
     int main()
     { 
     	int i,x,y,z;
     	memset(a,127/3,sizeof(a));//置为无穷大
    	 for(i=1;i<=n;i++)
    	 a[i][i]=0;//自身距离为0 
     	cin>>n>>m;
     	for(i=1;i<=m;i++)
     	{ 
     		cin>>x>>y>>z;
     		a[x][y]=a[y][x]=min(z,a[x][y]);
    	 }
    	 djstra(1);
    	 if(d[n]>9999999)
    	 cout<<-1;
    	 else 
    	 cout<<d[n]; 
    	 return 0;
     }

打印路径：

#include<iostream>//迪杰斯特拉算法求最短路径 （无向网） 
    #include<cstring>
    using namespace std;
    int a[105][105],d[105],v[105],path[105],n,m;
    //数组a存储边和权值，数组d存储从某个源点start到i的最短路径，数组v记录i是否被用来刷新过数组d，path记录路径
    int GetMin()//获取start和i之间最小权值且未被访问过的点的下标 
    { 
    	int minv=1e9,mini,i;
    	for(i=1;i<=n;i++)
    	{ 
    		if(v[i]==0&&d[i]<minv)
    		minv=d[i],mini=i;
    	}
    	return mini;
     } 
     void djstra(int start)
     { 
     	int i,j;
     	v[start]=1;
     	for(i=1;i<=n;i++)
     	d[i]=a[start][i],path[i]=start;
     	for(i=1;i<n;i++)
     	{ 
     		int u=GetMin();//获取最佳的u来刷新 
     		v[u]=1;
     		for(j=1;j<=n;j++)
     		if(d[j]>d[u]+a[u][j])
    		d[j]=d[u]+a[u][j],path[j]=u;
    	 }
     }
     void printpath(int x)
     { 
     	if(x==1)
     	{ 
     		cout<<x<<' ';
     		return ;
    	 }
     	
     	printpath(path[x]);
     	cout<<x<<' ';
     	
     }
     int main()
     { 
     	int i,x,y,z;
     	memset(a,127/3,sizeof(a));//置为无穷大
    	 for(i=1;i<=n;i++)
    	 a[i][i]=0;//自身距离为0 
     	cin>>n>>m;
     	for(i=1;i<=m;i++)
     	{ 
     		cin>>x>>y>>z;
     		a[x][y]=a[y][x]=min(z,a[x][y]);
    	 }
    	 djstra(1);
    	 if(d[n]>9999999)
    	 cout<<-1<<endl;
    	 else 
    	 cout<<d[n]<<endl;
    	 printpath(n); 
    	 return 0;
     }