交通规划(csp最详细题解100分代码---最小最短路径树)|江阴雨辰互联

2023年7月30日发(作者：)

交通规划（csp最详细题解100分代码---最⼩最短路径树）问题描述　　G国国王来中国参观后，被中国的⾼速铁路深深的震撼，决定为⾃⼰的国家也建设⼀个⾼速铁路系统。　　建设⾼速铁路投⼊⾮常⼤，为了节约建设成本，G国国王决定不新建铁路，⽽是将已有的铁路改造成⾼速铁路。现在，请你为G国国王提供⼀个⽅案，将现有的⼀部分铁路改造成⾼速铁路，使得任何两个城市间都可以通过⾼速铁路到达，⽽且从所有城市乘坐⾼速铁路到⾸都的最短路程和原来⼀样长。请你告诉G国国王在这些条件下最少要改造多长的铁路。输⼊格式　　输⼊的第⼀⾏包含两个整数n, m，分别表⽰G国城市的数量和城市间铁路的数量。所有的城市由1到n编号，⾸都为1号。　　接下来m⾏，每⾏三个整数a, b, c，表⽰城市a和城市b之间有⼀条长度为c的双向铁路。这条铁路不会经过a和b以外的城市。输出格式　　输出⼀⾏，表⽰在满⾜条件的情况下最少要改造的铁路长度。样例输⼊4 51 2 41 3 52 3 22 4 33 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。输⼊保证每个城市都可以通过铁路达到⾸都。　　解题思路：　　呃。。第⼀眼看成了求最⼩⽣成树的问题，（然后仔细⼀看其实不是），注意这句话：**⽽且从所有城市乘坐⾼速铁路到⾸都的最短路程和原来⼀样长。　　也就是说每个城市到⾸都的最短路径必须要修建铁路，找到这个最短路径所需要的最少花费（即要改造的长度最⼩），即求所有顶点到⾸都的最短路问题。⽤spfa算法或者dijstra算法都可以。不清楚这两个算法的可以看我这两篇⽂章：不过注意我们需要求出这条路径的最短花费，光借助dis数组保存源点到各点的最短距离是不够的，还需要借助⼀个cost数组。cost数组⾥存放的是到这个点的前⼀条边的最短花费。注意：当某个点加上它的两个前驱边距离长度与源点到这个点的最短距离都相等的时候，我们要找它前驱花费最⼩的那条边。如图所⽰：当源点到3的最短距离都是5的时候，我们不能选择1-3这条前驱边，⽽是选择4-3这条前驱边，因为这条前驱边⽐1-3的边⼩，更有利于整体的花费最⼩。如图：因为最终的答案肯定是由n-1条边构成的⽣成树，由图看出：选择1-2，2-4，4-3这三条边⽐1-2，2-4，1-3这三条边整体的花费要少。所以我们最终计算出cost[2]-cost[n]每个顶点的前⼀条边的最⼩花费的总和，就是所要求的题⽬答案。这⾥我⽤的是spfa算法**，下⾯我们来看代码吧，都有详细注释，⽅便读者阅读。#include using namespace std;#define inf 0x3f3f3fclass Edg //定义边类（结构体）

{ public: int d;//邻接点

int w; //权值（距离或花费）

Edg(int num,int weight)//类的初始化

{ d=num; w=weight; }};vectorG[10001];//定义图的邻接表

bool book[10001];//标志数组，表⽰这个点在不在队列中

int n,m,cost[10001];//n为顶点数，m为边数，cost表⽰到这个点的前⼀条边的最⼩距离

vector dis(10001,inf); //dis存储源点到每⼀条边的最短距离

void spfa(int source){ dis[source]=0;//初始化源点到⾃⾝距离为0

queue q; (source);//源点⼊队列

while(!())//当队列⾮空时

{ int f=(); //取出队⾸元素

();//然后把它从队列⾥踢出去