算是一道需要动脑筋的最短路问题了，关键在于建图部分，对于n个电梯中每一个都要经过cnt个楼层，a[0],a[1],a[2],a[3],a[4],......a[cnt-1],那么对于任意两个楼层a[j],a[l],都需要建立一条a[j]到a[l]的边，以及另一条反向边。而且为了表示所属的电梯，另外用一个数组tag[e]表示边e所属的电梯，当tag[e1]!=tag[e2]，应该在时间上加上60s。然后利用dijsktra+优先队列即可。
最近感觉做acm题是真真的开始入门了，不过接触到的算法，是在是少，一步一步慢慢学精吧。坚持做到每天独立的切几题，这样的成就感一定能够使得我越走越远。
#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN 200
#define MAXM 30000
#define INF 1000000000 using namespace std;
typedef pair<int, int> pii; int first[MAXN], T[], a[MAXN], d[MAXN], pa[MAXN];
int next[MAXM], u[MAXM], v[MAXM], w[MAXM], tag[MAXM];
int i, n, k, cnt, e; void add_edge(int from, int to, int c)
{
u[e] = from;
v[e] = to;
next[e] = first[from];
w[e] = c;
tag[e] = i;
first[from] = e++;
}
void read_graph(void)
{
for(int j = ; j < cnt; j++)
for(int l = j + ; l < cnt; l++)
{
add_edge(a[j], a[l],(a[l] - a[j]) * T[i]);
add_edge(a[l], a[j],(a[l] - a[j]) * T[i]);
}
}
int cmp(int e1, int e2)
{
if(e1 == -)
return ;
if(tag[e1] == tag[e2])
return ;
return ;
}
priority_queue<pii, vector<pii>, greater<pii> > q; int main(void)
{
while(~scanf("%d%d", &n, &k))
{
char ch;
e = ;
memset(first, -, sizeof(first));
memset(pa, -, sizeof(pa));
for(i = ; i <= n; i++)
scanf("%d", T + i);
for(i = ; i <= n; i++)
{
cnt = ;
while()
{
scanf("%d%c", &a[cnt], &ch);
cnt++;
if(ch == '\n')
{
read_graph();
// printf("%d\n", cnt);
break;
}
}
}
// printf("%d\n", e);
for(int j = ; j < ; j++)
d[j] = INF;
d[] = ;
q.push(make_pair(d[],));
while(!q.empty())
{
pii u = q.top();
q.pop();
int x = u.second;
if(d[x] != u.first)
continue;
for(int ee = first[x]; ee != -; ee = next[ee])
if(d[v[ee]] > d[x] + w[ee] + cmp(pa[x],ee))
{
d[v[ee]] = d[x] + w[ee] + cmp(pa[x],ee);
// printf("%d\n", cmp(pa[ee], ee));
q.push(make_pair(d[v[ee]],v[ee]));
pa[v[ee]] = ee;
}
}
if(d[k] == INF)
puts("IMPOSSIBLE");
else printf("%d\n",d[k]);
}
return ;
}