(1) 二分
? ? 把所有的高度都拿過(guò)來(lái),組合起來(lái),sort一遍,然后二分,找到能連通的最小的那個(gè),但這里存在一起情況,就是遇到高度差相等的時(shí)候會(huì)bug....

(2) 枚舉 連通直接break
? ? 把所有的高度都拿過(guò)來(lái),組合起來(lái),soet一遍,然后暴力枚舉上下限制,能連通直接break;這個(gè)顯然是錯(cuò)的,直接break的話(huà)只能保證高度差最小,不能保證路徑最短..

(3) 枚舉 連通并且高度變化的時(shí)候 break;就是在(2)的基礎(chǔ)上不直接break,如果第一次找到能連接1,n的路徑直接記錄當(dāng)前高度差,然后一直往后跑到高度差不等于第一次連通的高度差的時(shí)候break;這樣做肯定是對(duì)的,但是時(shí)間復(fù)雜度我感覺(jué)過(guò)不去....

(4) 寫(xiě)到第三部我突然想到一個(gè)自己感覺(jué)正確的方法,因?yàn)槭謶芯筒粚?xiě)那個(gè)代碼了,直接說(shuō)思路,就是hash + 二分,我們枚舉出所有范圍組合的后排序,排序后吧所有高度差相同的hash成一個(gè)點(diǎn),每次如果這個(gè)點(diǎn)中的某一個(gè)點(diǎn)使其連通了,那么這個(gè)點(diǎn)就是可行點(diǎn)(如果多個(gè)都滿(mǎn)足記得保留最優(yōu)),直接mid = up = mid - 1.......,感覺(jué)這樣應(yīng)該會(huì)好點(diǎn)..雖然沒(méi)有去實(shí)現(xiàn),感覺(jué)會(huì)優(yōu)化很多時(shí)間吧...

下面是(3)的代碼,雖然ac了,但自認(rèn)為會(huì)TLE..

#include<stdio.h> #include<string.h> #include<queue> #include<algorithm>#define N_node 100 + 20 #define N_edge 10000 + 500 #define INF 2000000000 using namespace std;typedef struct {int to ,next ,cost; }STAR;typedef struct {int low ,up ,d; }HHH;STAR E[N_edge]; HHH DH[100*100+100]; int list[N_node] ,tot; int s_x[N_node]; int H[N_node];void add(int a, int b ,int c) {E[++tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot; }bool camp(HHH a ,HHH b) {return a.d < b.d; }int abss(int x) {return x > 0 ? x : -x; }void SPFA(int s ,int n ,int low ,int up) {for(int i = 0 ;i <= n ;i ++)s_x[i] = INF;int mark[N_node] = {0};s_x[s] = 0;mark[s] = 1;queue<int>q;q.push(s);while(!q.empty()){int tou ,xin;tou = q.front();q.pop();mark[tou] = 0;for(int k = list[tou] ;k ;k = E[k].next){xin = E[k].to;if(H[xin] < low || H[xin] > up) continue;if(s_x[xin] > s_x[tou] + E[k].cost){s_x[xin] = s_x[tou] + E[k].cost;if(!mark[xin]){mark[xin] = 1;q.push(xin);}}}}return ; }int main () {int t ,i ,j ,n ,m;int a ,b ,c;scanf("%d" ,&t);while(t--){scanf("%d %d" ,&n ,&m);for(i = 1 ;i <= n ;i ++)scanf("%d" ,&H[i]);memset(list ,0 ,sizeof(list));tot = 1;for(i = 1 ;i <= m ;i ++){scanf("%d %d %d" ,&a ,&b ,&c);add(a,b,c);add(b,a,c);}int tmp = 0;for(i = 1 ;i <= n ;i ++)for(j = i + 1 ;j <= n ;j ++){int low = H[i] < H[j] ? H[i] : H[j];int up = H[i] > H[j] ? H[i] : H[j];DH[++tmp].low = low;DH[tmp].up = up;DH[tmp].d = up - low;} sort(DH + 1 ,DH + tmp + 1,camp);int minc = INF,minz = 0;for(i = 1 ;i <= tmp ;i ++){if(H[1] < DH[i].low || H[1] > DH[i].up) continue;if(H[n] < DH[i].low || H[n] > DH[i].up) continue;SPFA(1 ,n ,DH[i].low ,DH[i].up);if(s_x[n] == INF) continue;if(minc == INF){minc = DH[i].d;minz = s_x[n];}else{if(minc != DH[i].d) break;if(s_x[n] < minz)minz = s_x[n];} } if(n == 1) printf("0 0\n");else printf("%d %d\n" ,minc ,minz);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu2363 枚举最短路的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。