Question

数据结构c 语言版题目，求代码!!! 请一定用C语言，求大神帮忙

小L居住的地方有很多城市，每个城市编号从1到n，城市之间共有m条道路相连，这些道路每一条都有一个固定的行驶速度V。
一天，小L要从城市S出发去另一个城市T游玩，连接这些城市的每条道路都有一个固定的行驶速度V，现在小L想知道从S出发到T所经过的道路中最大速度Vmax和最小速度Vmin最小差值是多少？输入数据保证S一定可以到达T。
两个城市可能有多条道路。

输入：一个整数Q，代表有多少组测试数据。
接下来对每组测试数据：
第1行:n、m，城市数目和道路数目。
第2~m+1行：3个整数Ui,Vi,Wi, (i=1,…..,M)，道路的两个城市编号和道路的行驶速度。
最后一行：两个整数S T ,代表起点和终点的城市编号。

约束条件：
2≤Q≤5 ，1<n≤500，0<m≤5000, 1≤ Ui, Vi , S , T ≤n, 0< Wi <30000，

输出：一个整数代表所求最小差值。

样例输入：
2
3 2
1 2 1
2 3 3
1 3
3 3
1 2 6
1 2 5
2 3 8
1 3
样例输出：
2
2
求详细的代码

Answer 1

如图

源代码:

/*
小L居住的地方有很多城市...
作者:q839219286
算法思想：城市图采用DFS搜索，搜索终止条件是：到达终点或 Vmax-Vmin＞dV
设 dV=Vmax-Vmin，求dV的方法是利用 Vmax、Vmin的递归历史记录
图结构采用“邻接表”法，存储结构采用数组。
*/
//C语言版
#include<stdio.h>
#include<stdlib.h>
#include <limits.h>
//宏定义函数
#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<Q ; i++) {
		buildGraph();	//scanf已包含在内
		DFS(start, -1, INT_MAX-1);
		out[i] = minDIF;
	}
	//输出最终结果
	for (i = 0; i<Q; 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;
}

Answer 2

q=pp=Lwhile(p->next!=q)p->next;s->next=p->nextP->next=s;5,7,3，1,2

追问

大神可以给一下详细的代码吗，求求大神帮帮忙，学渣真的做不来

Answer 3

我猜你是hdu的