如图
源代码:
/*
小L居住的地方有很多城市...
作者:q839219286
算法思想：城市图采用DFS搜索，搜索终止条件是：到达终点或 Vmax-Vmin＞dV
设 dV=Vmax-Vmin，求dV的方法是利用 Vmax、Vmin的递归历史记录
图结构采用“邻接表”法，存储结构采用数组。
*/
//C语言版
#include
#include
#include
//宏定义函数
#define MAX(a,b) (a)>(b)?(a):(b)
#define MIN(a,b) (a)<(b)?(a):(b)
//图节点结构（邻接表法）
struct VNode {
struct Edge *next;
char visited; //是否在本路径中访问过，=1是；=0否
};
//图的边结构（邻接表法）
struct Edge {
int v; //道路的行驶速度
struct VNode *adjVex; //道路通向的城市节点
struct Edge *next;
};
#define max_Vex 500
#define max_Edge 5000
//最多500个城市（其中下标为0不使用）
struct VNode vex[max_Vex + 1];
struct Edge edge[max_Edge * 2]; //一条边有两个节点需要记录
int vex_Num, edge_Num;
struct VNode *start, *end; //起点、终点
int minDIF; //已经找到的通往终点路径中Vmax-Min的最小差值
void addEdge(int Ui, int Vi, int Wi);//新增 Ui 通往 Vi的道路
void buildGraph();
void DFS(struct VNode *vex, int Vmax, int Vmin);
int main() {
int Q; scanf("%d", &Q); //一个整数Q，代表有多少组测试数据。
int out[5],i; //2≤Q≤5
for (i=0; i buildGraph(); //scanf已包含在内
DFS(start, -1, INT_MAX-1);
out[i] = minDIF;
}
//输出最终结果
for (i = 0; i printf("%d\n",out[i] );
}
//getchar(); getchar(); //防止闪退
return 0;
}
void DFS(struct VNode *vex,int Vmax,int Vmin) {
if (Vmax - Vmin >= minDIF)return; //一旦超限，则没有继续遍历的意义
if (vex == end) { //到达终点
minDIF = Vmax - Vmin; //已经保证 Vmax - Vmin < minDIF
}else { //继续遍历
vex->visited = 1; //防止DFS无限循环
struct Edge *next;
for (next = vex->next;
next != NULL; next = next->next) {
if(0== next->adjVex->visited) //下一节点不在已走过的节点
DFS(next->adjVex, MAX(next->v, Vmax), MIN(next->v, Vmin));
}
vex->visited = 0; //时光倒流
}
}
//新增 Ui 通往 Vi的道路
void addEdge(int Ui, int Vi, int Wi) {
edge[edge_Num].adjVex = vex + Vi;
edge[edge_Num].v = Wi;
edge[edge_Num].next = vex[Ui].next; //链表头插法
vex[Ui].next = edge+ edge_Num;
edge_Num++;
}
void buildGraph() {
int road_Num, i, startID, endID;
struct VNode *p_V;
scanf("%d %d", &vex_Num, &road_Num);
//初始化节点。倒序遍历,注意vex[0]不算入。 其实可以用memset()秒杀的，我写的是原生代码版本
for (p_V = vex + vex_Num; p_V > vex; p_V--) {
p_V->next = NULL;
p_V->visited = 0;
}
//注意 road_Num条道路 有 2*edge_Num 个邻接表边
edge_Num = 0;
for (; road_Num > 0; road_Num--) { //road_Num条道路 读入road_Num行数据
int Ui, Vi, Wi;//3个整数Ui,Vi,Wi, (i=1,…..,M)，道路的两个城市编号和道路的行驶速度。
scanf("%d %d %d", &Ui, &Vi, &Wi);
//注意两个方向都要添加
addEdge(Ui, Vi, Wi);
addEdge(Vi, Ui, Wi);
}
//余下数据赋值
scanf("%d %d", &startID, &endID);
start = vex + startID;
end = vex + endID;
minDIF = INT_MAX;
}
