CCF CSP 交通规划 最短路径+最小生成树

时间：2022-02-20 23:16:28
G国国王来中国参观后，被中国的高速铁路深深的震撼，决定为自己的国家也建设一个高速铁路系统。
　　建设高速铁路投入非常大，为了节约建设成本，G国国王决定不新建铁路，而是将已有的铁路改造成高速铁路。现在，请你为G国国王提供一个方案，将现有的一部分铁路改造成高速铁路，使得任何两个城市间都可以通过高速铁路到达，而且从所有城市乘坐高速铁路到首都的最短路程和原来一样长。请你告诉G国国王在这些条件下最少要改造多长的铁路。
输入格式
　　输入的第一行包含两个整数n, m，分别表示G国城市的数量和城市间铁路的数量。所有的城市由1到n编号，首都为1号。
　　接下来m行，每行三个整数a, b, c，表示城市a和城市b之间有一条长度为c的双向铁路。这条铁路不会经过a和b以外的城市。
输出格式
　　输出一行，表示在满足条件的情况下最少要改造的铁路长度。
样例输入
4 5
1 2 4
1 3 5
2 3 2
2 4 3
3 4 2
样例输出
11
评测用例规模与约定
　　对于20%的评测用例，1 ≤ n ≤ 10，1 ≤ m ≤ 50；
　　对于50%的评测用例，1 ≤ n ≤ 100，1 ≤ m ≤ 5000；
　　对于80%的评测用例，1 ≤ n ≤ 1000，1 ≤ m ≤ 50000；
　　对于100%的评测用例，1 ≤ n ≤ 10000，1 ≤ m ≤ 100000，1 ≤ a, b ≤ n，1 ≤ c ≤ 1000。输入保证每个城市都可以通过铁路达到首都。

————————————————————————————————————————

这题看着既像最小生成树的问题，也像最短路径的问题，其实是两个问题的一个结合吧。想想迪杰斯特拉算法和Prime算法其实挺像的，都是从一个点出发搜索路径，最终形成一颗到达所有点的树。这两个算法其实在操作中区别仅是选择哪一个点加入的判据。迪杰斯特拉算法每次选择加入哪一个点的依据是哪个点到达起始点距离最短。而Prime算法则不需要比较到达起始点的总路径长度，只需要比较到达上一个点的距离。

这题其实是在迪杰斯特拉算法找最短路径的基础上，增加最小生成树的判断。如何插入最小生成树的判断呢？当判断最小路径时，有两个点到达起始点的距离相同的，那么这个时候再按Prime算法判断，选择添加到达上一个点最短的那条路径。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAXX 10010
#define INF 0x3f3f3f
struct Rode{
	int to;
	int distance;
}R;
struct Node{
	int beg;
	int distance;//beg到to节点的距离 
	int all;//to到节点1的总距离 
}N[MAXX];
int num;
int n,m;
vector<struct Rode> vec[MAXX];//邻接表 
bool get_node[MAXX];
void Di_Prime(int begin)
{
	get_node[begin]=true;//标记节点1已经加入
	for(int i=0;i<vec[begin].size();i++)//将与节点1相邻的边加入 
	{
		int to = vec[begin][i].to;
		N[to].beg = begin;
		N[to].all = N[to].distance = vec[begin][i].distance;
	}
	int nn=n;
	nn--;//剩余n个节点需要加入 
	while(nn>0)
	{
		nn--; 
		int t_dis=INF,t_i=0,t_all = INF; 
		for(int i=1;i<=n;i++)
		{
				if(N[i].all < t_all)
			{
				t_all = N[i].all;
				t_i = i;
				t_dis = N[i].distance;
			}else if(N[i].all == t_all)//当迪杰斯特拉判断最短路径判断相同时，用Prime算法判断 
			{
				if(N[i].distance < t_dis)
				{
					t_all = N[i].all;
				    t_i = i;
				    t_dis = N[i].distance;
				}
			}
		}
		num+=t_dis;
		get_node[t_i]=true;//标记节点t_i已经加入
	    for(int i=0;i<vec[t_i].size();i++)//将与节点t_i相邻的边加入 
	    {
	    	int to = vec[t_i][i].to;
	    	int dis = vec[t_i][i].distance;
	   	    if(!get_node[to])
	    	{
	    		if( N[t_i].all + vec[t_i][i].distance < N[to].all )
	    		{
	    		    N[to].beg = t_i;
	 	            N[to].distance = vec[t_i][i].distance;
	 	            N[to].all = N[t_i].all + vec[t_i][i].distance;
	 	   		}
				else if(N[t_i].all + vec[t_i][i].distance == N[to].all)
	    		{
	    			//当迪杰斯特拉判断最短路径判断相同时，用Prime算法判断 
	    			if(vec[t_i][i].distance < N[to].distance)
	    			{
					    N[to].beg = t_i;
	 	                N[to].distance = vec[t_i][i].distance;
	     	            N[to].all = N[t_i].all + vec[t_i][i].distance;	
	    			}
				} 
	    	}
	    }
	    N[t_i].distance = INF;
		N[t_i].all = INF;
	}
}
int main()
{
	int t1,t2,t3;
	cin >> n >> m;
	for(int i=0;i<m;i++)
	{
		cin >> t1 >> t2 >> t3;
		R.to = t1;
		R.distance = t3;
		vec[t2].push_back(R);
		R.to = t2;
		vec[t1].push_back(R);
	}
	for(int i=0;i<=n;i++)
	{
		N[i].all = N[i].beg = N[i].distance = INF;
	}
	Di_Prime(1);
	cout << num << endl;
	return 0;
}

标签：

相关文章