解题报告

思路

神奇的电梯，我的思路是直接整出一个超级源点和超级汇点（貌似这是网络流的叫法，，，ｓａｄ）

源点与所有有在０层的电梯连线，汇点与ｋ层连线，然后每个电梯如果有在同一层的连６０ｓ的线，对于每个电梯可以到达的每一层连一条线，处理层和电梯就直接用类似于离散化的方式处理，比如说第一个电梯可以有ｎ个层可以到，第二个电梯有ｍ个层可以到，那么就有１－ｎ＋ｍ的点，源点０，汇点ｎ＋ｍ＋１；

做完看来别人的解题报告，发现我的想法很辍，因为只有在换电梯的时候才要松弛加上６０，用邻接矩阵处理就很好。

智商捉急，感叹都是数据太弱。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define inf 0x3f3f3f3f
#define M 1000000
#define N 100000
using namespace std;
struct node {
    int v,w,next;
} edge[M];

int head[N],vis[N],dis[N],cnt,n,m,k;
int ttme[10],num[10],lift[10][1100],kl[1100],S,T;
void add(int u,int v,int w) {
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void spfa() {
    for(int i=S; i<=T; i++) {
        dis[i]=inf;
        vis[i]=0;
    }
    vis[S]=1;
    dis[S]=0;
    queue<int>Q;
    Q.push(S);
    while(!Q.empty()) {
        int u=Q.front();
        Q.pop();
        vis[u]=0;
        for(int i=head[u]; i!=-1; i=edge[i].next) {
            int v=edge[i].v;
            if(dis[v]>dis[u]+edge[i].w) {
                dis[v]=dis[u]+edge[i].w;
                if(!vis[v]) {
                    vis[v]=1;
                    Q.push(v);
                }
            }
        }
    }
}
int main() {
    int i,j;
    while(~scanf("%d%d",&n,&k)) {
        memset(head,-1,sizeof(head));
        cnt=0;
        char c;
        for(i=1; i<=n; i++)
            scanf("%d",&ttme[i]);
        memset(num,0,sizeof(num));
        for(i=1; i<=n; i++) {
            while(~scanf("%d%c",&lift[i][++num[i]],&c))
                if(c=='\n')break;
        }
        int ct1=0;
        int sum=0,sum1=0;
        for(i=1; i<=n; i++) {
            sum+=num[i-1];
            for(j=1; j<=num[i]; j++) {
                if(lift[i][j]==k) {
                    kl[ct1++]=j+sum;
                }
                for(int l=1; l<=num[i]; l++) {
                    if(j!=l)
                        add(j+sum,l+sum,abs(lift[i][l]-lift[i][j])*ttme[i]);
                }
            }
        }
        S=0;
        sum+=num[n];
        T=sum+1;
        sum=sum1=0;
        for(i=1; i<=n; i++) {
            sum+=num[i-1];
            sum1=0;
            for(j=1; j<=n; j++) {
                sum1+=num[j-1];
                if(i!=j) {
                    for(int l=1; l<=num[i]; l++) {
                        for(int f=1; f<=num[j]; f++) {
                            if(lift[i][l]==lift[j][f]) {
                                add(l+sum,f+sum1,60);
                            }
                        }
                    }
                }
            }
        }
        for(i=0; i<ct1; i++) {
            add(kl[i],T,0);
            add(T,kl[i],0);
        }
        sum=0;
        for(i=1; i<=n; i++) {
            sum+=num[i-1];
            if(lift[i][1]==0) {
                add(S,sum+1,0);
                add(sum+1,S,0);
            }
        }
        spfa();
        if(dis[T]==inf)
            printf("IMPOSSIBLE\n");
        else
            printf("%d\n",dis[T]);
    }
    return 0;
}

Robert Rodriguez, "Four Rooms."

A skyscraper has no more than 100 floors, numbered from 0 to 99. It has n (1<=n<=5) elevators which travel up and down at (possibly) different speeds. For each i in {1, 2,... n}, elevator number i takes T_i (1<=T_i<=100) seconds to travel between any two adjacent floors (going up or down). Elevators do not necessarily stop at every floor. What‘s worse, not every floor is necessarily accessible by an elevator.

You are on floor 0 and would like to get to floor k as quickly as possible. Assume that you do not need to wait to board the first elevator you step into and (for simplicity) the operation of switching an elevator on some floor always takes exactly a minute. Of course, both elevators have to stop at that floor. You are forbiden from using the staircase. No one else is in the elevator with you, so you don‘t have to stop if you don‘t want to. Calculate the minimum number of seconds required to get from floor 0 to floor k (passing floor k while inside an elevator that does not stop there does not count as "getting to floork").

Input
The input will consist of a number of test cases. Each test case will begin with two numbers, n and k, on a line. The next line will contain the numbers T₁, T₂,... T_n. Finally, the next n lines will contain sorted lists of integers - the first line will list the floors visited by elevator number 1, the next one will list the floors visited by elevator number 2, etc.

Output

For each test case, output one number on a line by itself - the minimum number of seconds required to get to floor k from floor 0. If it is impossible to do, print "IMPOSSIBLE" instead.

2 30
10 5
0 1 3 5 7 9 11 13 15 20 99
4 13 15 19 20 25 30
2 30
10 1
0 5 10 12 14 20 25 30
2 4 6 8 10 12 14 22 25 28 29
3 50
10 50 100
0 10 30 40
0 20 30
0 20 50
1 1
2
0 2 4 6 8 10

275
285
3920
IMPOSSIBLE

Explanation of examples

In the first example, take elevator 1 to floor 13 (130 seconds), wait 60 seconds to switch to elevator 2 and ride it to floor 30 (85 seconds) for a total of 275 seconds.

In the second example, take elevator 1 to floor 10, switch to elevator 2 and ride it until floor 25. There, switch back to elevator 1 and get off at the 30‘th floor. The total time is 
10*10 + 60 + 15*1 + 60 + 5*10 = 285 seconds.

In example 3, take elevator 1 to floor 30, then elevator 2 to floor 20 and then elevator 3 to floor 50.

In the last example, the one elevator does not stop at floor 1.

UVa10801_Lift Hopping(最短路)(小白书图论专题)