å¦å¾
æºä»£ç :
/*
å°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;
}