UVA 10801 Lift Hopping
这个题的意思是说，一个人在一个奇怪的宾馆里，这个宾馆有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;
}
补充：软件开发 , C++ ,
