最短路

題意：有一棟樓100層，從0到99編號(hào)層數(shù)，有多部電梯（最多5部），給出每部每部電梯的速度，即上或下一層樓所用的秒數(shù)。然后每部電梯不一定在所有樓層出現(xiàn)，給你所有電梯可能出現(xiàn)的層數(shù)。給你一個(gè)目標(biāo)層，要你從0層開(kāi)始到目標(biāo)層，問(wèn)所用時(shí)間最短。在0層的時(shí)候選擇做哪步電梯出發(fā)不需要時(shí)間的，但是在中間的樓層，想換電梯的時(shí)候，需要60秒

這個(gè)題目看完就可以想到是最短路，每層樓是1個(gè)頂點(diǎn)，一共100個(gè)點(diǎn)，然后對(duì)于樓層而言可以通過(guò)電梯到達(dá)的話就是有一條邊，權(quán)值就是時(shí)間，那么可能出現(xiàn)平行邊，比如1號(hào)電梯可以從10樓到20樓，用時(shí)200秒，2號(hào)電梯也可以從10到20樓用時(shí)100秒……………………

這題，一開(kāi)始沒(méi)想那么多，用了鄰接表來(lái)建圖做，然后sample不過(guò)，然后調(diào)試一下發(fā)現(xiàn)了轉(zhuǎn)換電梯的時(shí)候會(huì)出錯(cuò)，然后思考了很久不知道怎么搞

一般的最短路其實(shí)都基于一個(gè)性質(zhì)就是都符合最優(yōu)子結(jié)構(gòu)的，但是這道題其實(shí)不符合最優(yōu)子結(jié)構(gòu)，因?yàn)檩啌Q增加的60秒破壞了最優(yōu)子結(jié)構(gòu)，看sample1的數(shù)據(jù)就可以知道，從0到30樓是要經(jīng)過(guò)15樓的，但是去15的時(shí)候卻不是最短的，我們是用2號(hào)電梯到達(dá)15樓，但是如果要去15樓的時(shí)間最短那么應(yīng)該是坐1號(hào)電梯，但是如果坐了1號(hào)電梯到15樓將無(wú)法滿足到30樓的時(shí)間最短，這其實(shí)有種為了最后的目標(biāo)的最優(yōu)解而舍近求遠(yuǎn)的感覺(jué)

?

后來(lái)想了一下，想了其實(shí)用鄰接表來(lái)建圖本身就是一個(gè)失敗的旋轉(zhuǎn)，如果是用鄰接矩陣來(lái)建圖，那么整個(gè)問(wèn)題就變得很簡(jiǎn)單

所以這個(gè)題目讓我想到師兄之前說(shuō)的一句話，做圖論講究經(jīng)驗(yàn)，尤其是什么問(wèn)題有什么來(lái)建圖這個(gè)很關(guān)鍵，這次算是體會(huì)到了

?

我寫(xiě)了3個(gè)版本，第一個(gè)普通的dij+鄰接矩陣 ， 第二個(gè)spfa+鄰接矩陣 ， 第三個(gè)優(yōu)先隊(duì)列dij+鄰接矩陣

3個(gè)版本只是改了求最短路的函數(shù)，讀取數(shù)據(jù)和建圖函數(shù)是一樣，都是鄰接矩陣建圖

至于為什么這樣建圖很難文字描述，可以仔細(xì)看第一份代碼的建圖（后面的建圖是一樣的），看代碼反而更容易懂

?

然后要AC還要注意三點(diǎn)

1.終點(diǎn)樓層可能就是0層，所以要特殊判斷，輸出0。

2.三個(gè)代碼中都是算多了一個(gè)60秒，就是從0層出發(fā)的時(shí)候算多一個(gè)60秒，但是題目說(shuō)不用的，所以最后答案減去1個(gè)60

3.三個(gè)代碼松弛都是 d[u]+g[u][v]+60 < d[v] ?， ?并不是說(shuō)換不換電梯都加60，而是在換電梯的時(shí)候才+60，為什么呢，看懂了建圖部分這個(gè)就懂了

?

第一個(gè)普通的dij+鄰接矩陣

#include <cstdio> #include <cstring> #define N 110 #define INF 0x3f3f3f3f int g[N][N],d[N],sp[10]; int s,t,n;void graph(int k,int ccount , int *m) {for(int i=1; i<=ccount; i++)for(int j=i+1; j<=ccount; j++){int u=m[i],v=m[j],w=(v-u)*sp[k];if(w<g[u][v])g[u][v]=g[v][u]=w;}return ; } void input() {int m[N],ccount; char ch;memset(g,0x3f,sizeof(g));for(int i=1; i<=n; i++) scanf("%d",&sp[i]);for(int i=1; i<=n; i++){ccount=0;while(1){scanf("%d",&m[++ccount]);ch=getchar();if(ch=='\n')break;}//for(int j=1; j<=ccount; j++)//printf("%d ",m[j]);//printf("\n");graph(i,ccount,m); //鄰接矩陣建圖 }return ; } void dij() {int fin[N];memset(d,0x3f,sizeof(d));memset(fin,0,sizeof(fin));d[s=0]=0;for(int nn=0; nn<99; nn++) //進(jìn)行n-1次 {int min=INF,u=s,flag=0;for(int i=0; i<=99; i++)if(!fin[i] && d[i]<min){ min=d[i]; u=i; flag=1; }if(!flag) break; //已經(jīng)找不到了即結(jié)束了fin[u]=1;for(int v=0; v<=99; v++) //松弛if(!fin[v] && d[u]+g[u][v]+60 < d[v])d[v]=d[u]+g[u][v]+60;}if(d[t]==INF)printf("IMPOSSIBLE\n");else if(t==s)printf("0\n");elseprintf("%d\n",d[t]-60); } int main() {while(scanf("%d%d",&n,&t)!=EOF){input();dij(); //dij鄰接矩陣 }return 0; }

?

?

?第二個(gè)spfa+鄰接矩陣

#include <cstdio> #include <cstring> #include <queue> using namespace std; #define N 110 #define INF 0x3f3f3f3f int g[N][N],d[N],sp[10]; int s,t,n;void graph(int k,int ccount , int *m) {for(int i=1; i<=ccount; i++)for(int j=i+1; j<=ccount; j++){int u=m[i],v=m[j],w=(v-u)*sp[k];if(w<g[u][v])g[u][v]=g[v][u]=w;}return ; } void input() {int m[N],ccount; char ch;memset(g,0x3f,sizeof(g));for(int i=1; i<=n; i++) scanf("%d",&sp[i]);for(int i=1; i<=n; i++){ccount=0;while(1){scanf("%d",&m[++ccount]);ch=getchar();if(ch=='\n')break;}//for(int j=1; j<=ccount; j++)//printf("%d ",m[j]);//printf("\n");graph(i,ccount,m); //鄰接矩陣建圖}return ; }void spfa() {queue<int> q;int vis[N];memset(vis,0,sizeof(vis));memset(d,0x3f,sizeof(d));d[s=0]=0; vis[s]=1;q.push(s);while(!q.empty()){int u=q.front(); vis[u]=0; q.pop();for(int v=0; v<=99; v++)if(d[u]+g[u][v]+60 < d[v]){d[v]=d[u]+g[u][v]+60;if(!vis[v]){q.push(v);vis[v]=1;}}}if(d[t]==INF)printf("IMPOSSIBLE\n");else if(t==s)printf("0\n");elseprintf("%d\n",d[t]-60);} int main() {while(scanf("%d%d",&n,&t)!=EOF){input();spfa();}return 0; }

?

?

第三個(gè)優(yōu)先隊(duì)列dij+鄰接矩陣

#include <cstdio> #include <cstring> #include <queue> #include <utility> #include <vector> using namespace std; #define N 110 #define INF 0x3f3f3f3f int g[N][N],d[N],sp[10]; int s,t,n; typedef pair<int , int> pii;void graph(int k,int ccount , int *m) {for(int i=1; i<=ccount; i++)for(int j=i+1; j<=ccount; j++){int u=m[i],v=m[j],w=(v-u)*sp[k];if(w<g[u][v])g[u][v]=g[v][u]=w;}return ; } void input() {int m[N],ccount; char ch;memset(g,0x3f,sizeof(g));for(int i=1; i<=n; i++) scanf("%d",&sp[i]);for(int i=1; i<=n; i++){ccount=0;while(1){scanf("%d",&m[++ccount]);ch=getchar();if(ch=='\n')break;}//for(int j=1; j<=ccount; j++)//printf("%d ",m[j]);//printf("\n");graph(i,ccount,m); //鄰接矩陣建圖}return ; }void dij() {priority_queue<pii,vector<pii>,greater<pii> > q; //優(yōu)先隊(duì)列3個(gè)參數(shù),變量類(lèi)型，容器類(lèi)型，比較算子int fin[N];memset(fin,0,sizeof(fin));memset(d,0x3f,sizeof(d));d[s=0]=0;q.push(make_pair(d[s],s));while(!q.empty()){pii p; int u;p=q.top(); q.pop();u=p.second; //點(diǎn)的標(biāo)號(hào)if(fin[u]) continue; //該點(diǎn)已經(jīng)計(jì)算過(guò)fin[u]=1; for(int v=0; v<=99; v++) //松弛if( d[u]+g[u][v]+60 < d[v] ){d[v]=d[u]+g[u][v]+60;q.push(make_pair(d[v],v));}}if(d[t]==INF)printf("IMPOSSIBLE\n");else if(t==s)printf("0\n");elseprintf("%d\n",d[t]-60); }int main() {while(scanf("%d%d",&n,&t)!=EOF){input();dij(); //dij優(yōu)先隊(duì)列}return 0; }

?

與50位技術(shù)專(zhuān)家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

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

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