這個題的意思是說，一個人在一個奇怪的賓館里，這個賓館有N個電梯，這些電梯相鄰兩層的時間為T(i),而且這些電梯很奇怪，只在某些樓層會停（每個電梯停下的頂層和底層都不一樣）。開始看的時候，把題意理解的巨復(fù)雜，覺得兩個樓層之間的轉(zhuǎn)移很難計算，后來才發(fā)現(xiàn)，換乘電梯需要的時間是固定的值(60s)，汗。這樣的話就是個最短路問題。不同電梯相同樓層之間的轉(zhuǎn)移花費是60s,相同電梯不同樓層之間的轉(zhuǎn)移花費是abs(i-j)*speed[n]。n是電梯號，i,j是樓層號。其實這個題可以用個無腦的BF算法搞一下，而且數(shù)據(jù)那么小。bf算法大概是這么個搞法:r[i][j][k][m]表示i個電梯到j(luò)層樓到j(luò)個電梯k層樓。轉(zhuǎn)移方程自己搞。什么？復(fù)雜度太高了？額，500X500X500,搞不起。這個題邊不太多，而且是單向邊，那就搞個spfa優(yōu)化下，應(yīng)該OK。不過我看了一天的重點不是這個，這個題我剛開始理解成每個電梯之間的轉(zhuǎn)移的代價不是固定的，然后就往分層圖的方向想了下，發(fā)現(xiàn)沒用。反正這種題的搞法就是最短路，如果能搞出個比較滿意的狀態(tài)出來，應(yīng)該能OK。想了下發(fā)現(xiàn)可以搞個r[i][j]表示第一層樓到達j個電梯j層樓的代價。好了，這就是個迪杰斯特拉嘛。。而且還是個赤裸裸的迪杰斯特拉，而且500^2的裸復(fù)雜度都無壓力。當時沒想到這個是個迪杰斯特拉，看錯題了以為每次轉(zhuǎn)移的代價不同。然后就開始yy了。yy了很久之后。。發(fā)現(xiàn)每次從一個點開始擴展，可以擴展出這么些個狀態(tài)：繼續(xù)坐這個電梯，走個遍;換乘電梯。那么這些狀態(tài)里面有一個最小的，不難證明這個最小的肯定就是狀態(tài)r[i][j]的最優(yōu)值了，因為如果他從別的地方走再回來，肯定會比這個值大的嘛。。好吧，這就是迪杰斯特拉了。我還暗暗驚嘆，原來迪杰斯特拉還可以這么玩，轉(zhuǎn)移的代價不確定，竟然也可以這么搞，當時就覺得劉汝佳出的題不錯。后來才發(fā)現(xiàn)題目也很普通。最近狀態(tài)很不好，想題目要很久，代碼也越寫越凌亂，索性正確率還不錯，早晚會出大麻煩?？赡芤彩莻€必經(jīng)的階段吧。加油，ws.
#include <iostream>
#include <sstream>
#include <cstdio>
#include <
string>
#include <cstring>
#include <algorithm>
#define INF ((1<<29) - 100)
using namespace std;
int nmap[6][110];
//第i個電梯能否到j(luò)層
int speed[6];
//第i個電梯的速度
int ndist[6][110];
int nvis[6][110];
int evlen[6];
int N,T;
void findmin(
int &minstx,
int &minsty)
{
int i,j;
minstx = minsty = -1;
for(i=0;i<N;i++)
for(j=0;j<100;j++)
{
if(nmap[i][j] && !nvis[i][j] && (ndist[minstx][minsty] > ndist[i][j] || minstx == -1))
{
minstx = i,minsty = j;
}
}
}
int getlen(
int j,
int minsty,
int m)
{
return abs(m - minsty)*speed[j];
}
void digs()
{
int i,j;
memset(nvis,0,
sizeof(nvis));
for(i=0;i<N;i++)
{
for(j=0;j<100;j++)
ndist[i][j] = INF;
}
for(i=0;i<N;i++)
if(nmap[i][0])
{
ndist[i][0] = 0;
}
int k;
for(i=0;i<N*100;i++)
{
int minstx = -1,minsty = -1;
findmin(minstx,minsty);
if(minstx == -1)
return;
nvis[minstx][minsty] = 1;
//printf("nidst:: %d %d %d\n",minstx,minsty,ndist[minstx][minsty]);
for(j=0;j<N;j++)
//沿著電梯上一層，或者等到下一個電梯，進入。
{
if(j == minstx)
{
int m = minsty + 1;
while(m != minsty)
{
if(nmap[j][m] && !nvis[j][m])
{
ndist[j][m] = min(ndist[j][m],ndist[j][minsty] + getlen(j,minsty,m));
}
m++,m%=100;
}
continue;
}
//等到j(luò)個電梯，minsty ,cost(ndist[minstx][minsty],minstx,j,minsty)
if(nmap[j][minsty] && !nvis[j][minsty])
{
ndist[j][minsty] = min(ndist[j][minsty],ndist[minstx][minsty] + 60);
}
}
}
}
int main()
{
int i,j;
string str;
while(scanf("%d%d",&N,&T) != EOF)
{
memset(nmap,0,
sizeof(nmap));
for(i=0;i<N;i++)
scanf("%d",&speed[i]);
getline(cin,str);
for(i=0;i<N;i++)
{
getline(cin,str);
stringstream ss(str);
int tmp,s=-1,e=-1;
while(ss>>tmp)
{
if(s == -1) s = tmp;
nmap[i][tmp] = 1;
e = tmp;
}
evlen[i] = e - s;
}
digs();
int ansx = -1;
for(i=0;i<N;i++)
if(nmap[i][T] && (ansx == -1 || ndist[ansx][T] > ndist[i][T]))
ansx = i;
if(ansx == -1 || ndist[ansx][T] == INF) printf("IMPOSSIBLE\n");
else printf("%d\n",ndist[ansx][T]);
}
return 0;
}