這個題的意思是說，一個人在一個奇怪的賓館裡，這個賓館有N個電梯，這些電梯相鄰兩層的時間為T(i),而且這些電梯很奇怪，只在某些樓層會停（每個電梯停下的頂層和底層都不一樣）。開始看的時候，把題意理解的巨復雜，覺得兩個樓層之間的轉移很難計算，後來才發現，換乘電梯需要的時間是固定的值(60s)，汗。這樣的話就是個最短路問題。不同電梯相同樓層之間的轉移花費是60s,相同電梯不同樓層之間的轉移花費是abs(i-j)*speed[n]。n是電梯號，i,j是樓層號。其實這個題可以用個無腦的BF算法搞一下，而且數據那麼小。bf算法大概是這麼個搞法:r[i][j][k][m]表示i個電梯到j層樓到j個電梯k層樓。轉移方程自己搞。什麼？復雜度太高了？額，500X500X500,搞不起。這個題邊不太多，而且是單向邊，那就搞個spfa優化下，應該OK。不過我看了一天的重點不是這個，這個題我剛開始理解成每個電梯之間的轉移的代價不是固定的，然後就往分層圖的方向想了下，發現沒用。反正這種題的搞法就是最短路，如果能搞出個比較滿意的狀態出來，應該能OK。想了下發現可以搞個r[i][j]表示第一層樓到達j個電梯j層樓的代價。好了，這就是個迪傑斯特拉嘛。。而且還是個赤裸裸的迪傑斯特拉，而且500^2的裸復雜度都無壓力。當時沒想到這個是個迪傑斯特拉，看錯題了以為每次轉移的代價不同。然後就開始yy了。yy了很久之後。。發現每次從一個點開始擴展，可以擴展出這麼些個狀態：繼續坐這個電梯，走個遍;換乘電梯。那麼這些狀態裡面有一個最小的，不難證明這個最小的肯定就是狀態r[i][j]的最優值了，因為如果他從別的地方走再回來，肯定會比這個值大的嘛。。好吧，這就是迪傑斯特拉了。我還暗暗驚歎，原來迪傑斯特拉還可以這麼玩，轉移的代價不確定，竟然也可以這麼搞，當時就覺得劉汝佳出的題不錯。後來才發現題目也很普通。最近狀態很不好，想題目要很久，代碼也越寫越凌亂，索性正確率還不錯，早晚會出大麻煩。可能也是個必經的階段吧。加油，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層
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個電梯，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;
}
