這個(gè)題的意思是說，一個(gè)人在一個(gè)奇怪的賓館里，這個(gè)賓館有N個(gè)電梯，這些電梯相鄰兩層的時(shí)間為T(i),而且這些電梯很奇怪，只在某些樓層會(huì)停（每個(gè)電梯停下的頂層和底層都不一樣）。開始看的時(shí)候，把題意理解的巨復(fù)雜，覺得兩個(gè)樓層之間的轉(zhuǎn)移很難計(jì)算，后來才發(fā)現(xiàn)，換乘電梯需要的時(shí)間是固定的值(60s)，汗。這樣的話就是個(gè)最短路問題。不同電梯相同樓層之間的轉(zhuǎn)移花費(fèi)是60s,相同電梯不同樓層之間的轉(zhuǎn)移花費(fèi)是abs(i-j)*speed[n]。n是電梯號(hào)，i,j是樓層號(hào)。其實(shí)這個(gè)題可以用個(gè)無腦的BF算法搞一下，而且數(shù)據(jù)那么小。bf算法大概是這么個(gè)搞法:r[i][j][k][m]表示i個(gè)電梯到j(luò)層樓到j(luò)個(gè)電梯k層樓。轉(zhuǎn)移方程自己搞。什么？復(fù)雜度太高了？額，500X500X500,搞不起。這個(gè)題邊不太多，而且是單向邊，那就搞個(gè)spfa優(yōu)化下，應(yīng)該OK。不過我看了一天的重點(diǎn)不是這個(gè)，這個(gè)題我剛開始理解成每個(gè)電梯之間的轉(zhuǎn)移的代價(jià)不是固定的，然后就往分層圖的方向想了下，發(fā)現(xiàn)沒用。反正這種題的搞法就是最短路，如果能搞出個(gè)比較滿意的狀態(tài)出來，應(yīng)該能OK。想了下發(fā)現(xiàn)可以搞個(gè)r[i][j]表示第一層樓到達(dá)j個(gè)電梯j層樓的代價(jià)。好了，這就是個(gè)迪杰斯特拉嘛。。而且還是個(gè)赤裸裸的迪杰斯特拉，而且500^2的裸復(fù)雜度都無壓力。當(dāng)時(shí)沒想到這個(gè)是個(gè)迪杰斯特拉，看錯(cuò)題了以為每次轉(zhuǎn)移的代價(jià)不同。然后就開始yy了。yy了很久之后。。發(fā)現(xiàn)每次從一個(gè)點(diǎn)開始擴(kuò)展，可以擴(kuò)展出這么些個(gè)狀態(tài)：繼續(xù)坐這個(gè)電梯，走個(gè)遍;換乘電梯。那么這些狀態(tài)里面有一個(gè)最小的，不難證明這個(gè)最小的肯定就是狀態(tài)r[i][j]的最優(yōu)值了，因?yàn)槿绻麖膭e的地方走再回來，肯定會(huì)比這個(gè)值大的嘛。。好吧，這就是迪杰斯特拉了。我還暗暗驚嘆，原來迪杰斯特拉還可以這么玩，轉(zhuǎn)移的代價(jià)不確定，竟然也可以這么搞，當(dāng)時(shí)就覺得劉汝佳出的題不錯(cuò)。后來才發(fā)現(xiàn)題目也很普通。最近狀態(tài)很不好，想題目要很久，代碼也越寫越凌亂，索性正確率還不錯(cuò)，早晚會(huì)出大麻煩。可能也是個(gè)必經(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個(gè)電梯能否到j(luò)層
int speed[6];
//第i個(gè)電梯的速度
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++)
//沿著電梯上一層，或者等到下一個(gè)電梯，進(jìn)入。
{
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ò)個(gè)電梯，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;
}