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[][];
int d[];
int t[];
int lift[];
int vis[];
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=, p;
memset(vis, , sizeof(vis));
vis[]=;
for(int i=; i<=; ++i){
int minLen=INF;
for(int j=; j<=; ++j){
if(!vis[j] && d[j] > d[root]+map[root][j]+)
d[j] = d[root]+map[root][j]+;
if(!vis[j] && minLen>d[j]){
minLen=d[j];
p=j;
}
}
if(minLen==INF)
return ;
root=p;
vis[root]=;
}
} int main(){
while(scanf("%d%d", &n, &k)!=EOF){
memset(map, 0x3f, sizeof(map));
memset(d, 0x3f, sizeof(d));
d[]=;
for(int i=; i<=n; ++i)
scanf("%d", &t[i]);
char ch; for(int i=; i<=n; ++i){
int cnt=;
while(){
scanf("%d%c", &lift[cnt++], &ch);
for(int j=; j<cnt-; ++j)
addEdge(lift[cnt-], lift[j], t[i]); if(ch=='\n')
break;
}
} Dijkstra(); if(k==)
printf("0\n");
else if(d[k]!=INF)
printf("%d\n", d[k]-);
else printf("IMPOSSIBLE\n");
}
return ;
}
上一篇:用EmEditor实现PDF转Word后的对齐排版


下一篇:Distributed Sentence Similarity Base on Word Mover's Distance