老了老了，這題思想有了，把這個思想變成代碼花了我好長的時間阿。。唉，不久一個Dijkstra么。
#include <stdio.h>
#include <string.h>
#define N 100
#define INF 1 << 28
int g[6][N][N], lift[6][N], top[6], mk[6][N], visit[6][N], dis[6][N];
void Init()
{
memset(mk, 0, sizeof(mk));
for(int k = 1; k < 6; k++)
{
for(int i = 0; i < N; i++)
{
g[k][i][i] = 0;
for(int j = i + 1; j < N; j++)
g[k][i][j] = g[k][j][i] = INF;
dis[k][i] = INF;
}
}
}
int Dijkstra(int n, int floorK)
{
memset(visit, 0, sizeof(visit));
for(int k = 1; k <= n; k++)
{
if(!lift[k][0]) dis[k][0] = 0;
}
while(1)
{
int mmin = INF, liftnum = -1, floor = -1;
for(int k = 1; k <= n; k++)
for(int j = 0; j < N; j++)
{
if(mk[k][j] && !visit[k][j] && dis[k][j] < mmin)
{
mmin = dis[k][j];
floor = j;
liftnum = k;
}
}
//printf("dis[%d][%d] = %d\n", liftnum, floor, dis[liftnum][floor]);
if(floor == floorK) return mmin;
if(floor == -1) return INF;
visit[liftnum][floor] = 1;
for(int k = 1; k <= n; k++)
for(int j = 0; j < N; j++)
{
if(mk[k][j] && !visit[k][j])
{
int tmp = dis[liftnum][floor] + g[k][floor][j];
if(k == liftnum)
{
if(tmp < dis[liftnum][j])
dis[liftnum][j] = tmp;
}
else if(j == floor)
{
// printf("k = %d, j = %d\n", k, j);
if(tmp + 60 < dis[k][j])
dis[k][j] = tmp + 60;
}
}
}
}
}
int main()
{
// freopen("in", "r", stdin);
int n, floorK, t[N];
char data[10 * N];
while(~scanf("%d %d", &n, &floorK))
{
Init();
for(int i = 1; i <= n; i++)
scanf("%d", &t[i]);
gets(data);
for(int i = 1; i <= n; i++)
{
gets(data);
char *p;
top[i] = 0;
p = strtok(data, " ");
while(p)
{
int a;
sscanf(p, "%d", &a);
mk[i][a] = 1;
lift[i][top[i]++] = a;
p = strtok(NULL, " ");
}
}
for(int k = 1; k <= n; k++)
{
for(int i = 0; i < top[k]; i++)
for(int j = i + 1; j < top[k]; j++)
{
int a = lift[k][i], b = lift[k][j];
g[k][a][b] = g[k][b][a] = (b - a) * t[k];
// printf("g[%d][%d][%d] = %d\n", k, a, b, g[k][a][b]);
}
}
int ans = Dijkstra(n, floorK);
if(ans == INF) puts("IMPOSSIBLE");
else printf("%d\n", ans);
}
return 0;
}