uva 10801 - Lift Hopping(最短路Dijkstra)-白红宇

题目大意：

就是一幢大厦中有0～99的楼层, 然后有1～5个电梯！每个电梯有一定的上升或下降速度和楼层的停止的位置！

问从第0层楼到第k层最少经过多长时间到达！

思路：明显的Dijkstra ，在建图的时候u->v可能有多个电梯到达，取时间最少的当作路径的权值！

如果我们发现 d[i] > d[j] + map[j][i] + 60, 那么说明从第0层到达第 i 层的时间大于从第j层

转移到其他电梯然后到达第 i 层的时间，那么就更新d[i]的值！

#include<iostream>

#include<cmath>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

int map[105][105];

int d[105];

int t[5];

int lift[105];

int vis[105];

int n, k;

void addEdge(int a, int b, int tt){

int dist=abs(a-b)*tt;

if(map[a][b]>dist)

map[a][b]=map[b][a]=dist;

}

void Dijkstra(){

int root=0, p;

memset(vis, 0, sizeof(vis));

vis[0]=1;

for(int i=1; i<=99; ++i){

int minLen=INF;

for(int j=1; j<=99; ++j){

if(!vis[j] && d[j] > d[root]+map[root][j]+60)

d[j] = d[root]+map[root][j]+60;

if(!vis[j] && minLen>d[j]){

minLen=d[j];

p=j;

}

if(minLen==INF)

return ;

root=p;

vis[root]=1;

}

int main(){

while(scanf("%d%d", &n, &k)!=EOF){

memset(map, 0x3f, sizeof(map));

memset(d, 0x3f, sizeof(d));

d[0]=0;

for(int i=1; i<=n; ++i)

scanf("%d", &t[i]);

char ch;

for(int i=1; i<=n; ++i){

int cnt=0;

while(1){

scanf("%d%c", &lift[cnt++], &ch);

for(int j=0; j<cnt-1; ++j)

addEdge(lift[cnt-1], lift[j], t[i]);

if(ch=='\n')

break;

}

Dijkstra();

if(k==0)

printf("0\n");

else if(d[k]!=INF)

printf("%d\n", d[k]-60);

else printf("IMPOSSIBLE\n");

}

return 0;

}

本文转自小眼儿博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3900059.html，如需转载请自行联系原作者