Lift Hopping UVA - 10801 建立一个“超级终点”

keywords: 图论

题意：

给你几个电梯，每个电梯有自己的运行速度，有自己可以到达的楼层。同一楼层换乘电梯需要花费60秒。求从0层出发，到达指定楼层最少时间花费。

分析：

如何建图，如何表示一个电梯楼层上下，如何表示换电梯，读入数据每一行并没有给具体有几个数字。

代码的最后，因为起点不止一个，终点不止一个，模仿超级源点，建立了一个超级终点。

示例代码：

// version01
// 读入数据的环节，给出了两个示范
// 建图的过程，感觉也需要细心操作，我就调试了好久
// 我要数组建图，开放链，跑堆优化的dijkstra

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e3 + 10, INF = 0x3f3f3f3f;

int n, ed;
int T[10];
vector<int> lift[10];
int g[10][N];

int d[N * 2];
bool vis[N * 2];

int h[N], e[N * 2], ne[N * 2], idx, w[N * 2];

void init(){
    for (int i = 1; i <= n; i++) cin >> T[i];

    for (int i = 1; i <= n; i++){
        lift[i].clear();

        int x; char c;
        while (scanf("%d%c", &x, &c) == 2){
            lift[i].push_back(x);
            g[i][x] = 1;

            if (c == '\n') break;
        }

        /*
        do{
            int x;
            cin >> x;
            lift[i].push_back(x);
            g[i][x] = 1;          //第i个电梯有x这层停靠
        }while (getchar() != '\n');
        */
    }
}

void add(int a, int b, int c){
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void build(){
    memset(h, -1, sizeof h);
    idx = 0;

    for (int i = 1; i <= n; i++){
        for (int j = 0; j < (int)lift[i].size(); j++){
            int now = lift[i][j];

            int b = i * 100 + now;
            if (j == 0){                       // 每个电梯的第一个可以到达的楼层
                if (now == 0){                   // 只有当这个楼层是第0层的时候，才能直接上(建边)
                    int w = T[i] * now;
                    add(0, b, w); add(b, 0, w);
                }
            }
            else{                             // 其他的情况，就是和前一个楼层建边即可
                int last = lift[i][j - 1];
                int a = i * 100 + last;
                int w = T[i] * abs(now - last);
                add(a, b, w); add(b, a, w);
            }

            // 暴力枚举前面的电梯有无j层停靠
            // 有停靠就60秒换乘
            for (int k = 1; k < i; k++)
                if (g[k][now]){              //第k个电梯也能到t层
                    int c = k * 100 + now;
                    add(c, b, 60); add(b, c, 60);
                }

        }
    }
}

void dijkstra(){
    memset(d, 0x3f, sizeof d);
    memset(vis, false, sizeof vis);

    d[0] = 0;
    priority_queue<PII> q;
    q.push(make_pair(0, 0));

    while (!q.empty()){
        PII t = q.top(); q.pop();
        int ver = t.second, dist = -t.first;

        if (vis[ver]) continue;
        vis[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i]){
            int j = e[i];
            if (dist + w[i] < d[j]){
                d[j] = dist + w[i];
                q.push(make_pair(-d[j], j));
            }
        }
    }
}

int getret(){
    int ret = INF;
    for (int i = 1; i <= n; i++){
        int p = i * 100 + ed;
        if (d[p] < ret) ret = d[p];
    }

    return ret;
}

int main(){
    while (cin >> n >> ed){
        init();
        build();
        dijkstra();

        int ret = getret();
        if (ret == INF) cout << "IMPOSSIBLE" << '\n';
        else cout << ret << '\n';
    }

    return 0;
}

// version02
// 看到超级源点，我们这里，感觉超级源点不好用，因为第一个样例第二个电梯，第一个到大的楼层是4
// 并不能从0层直接蹦到4层
// 最终求解答案的时候，我发现需要每个电梯遍历一遍，有有没有目标楼层停靠，更新ret
// 于是就建立了一个“超级终点”
// 然后直接输出d[super_ed]即可

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e3 + 10, INF = 0x3f3f3f3f;

int n, ed;
int T[10];
vector<int> lift[10];
int g[10][N];

int d[N * 2 + 10];
bool vis[N * 2];

int h[N], e[N * 2], ne[N * 2], idx, w[N * 2];

int super_ed = 10 * 100 + 10; 

void init(){
    for (int i = 1; i <= n; i++) cin >> T[i];

    for (int i = 1; i <= n; i++){
        lift[i].clear();

        int x; char c;
        while (scanf("%d%c", &x, &c) == 2){
            lift[i].push_back(x);
            g[i][x] = 1;

            if (c == '\n') break;
        }
    }
}

void add(int a, int b, int c){
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void build(){
    memset(h, -1, sizeof h);
    idx = 0;

    for (int i = 1; i <= n; i++){
        for (int j = 0; j < (int)lift[i].size(); j++){
            int now = lift[i][j];

            int b = i * 100 + now;
            if (j == 0){                       // 每个电梯的第一个可以到达的楼层
                if (now == 0){                   // 只有当这个楼层是第0层的时候，才能直接上(建边)
                    int w = T[i] * now;
                    add(0, b, w); add(b, 0, w);
                }
            }
            else{                             // 其他的情况，就是和前一个楼层建边即可
                int last = lift[i][j - 1];
                int a = i * 100 + last;
                int w = T[i] * abs(now - last);
                add(a, b, w); add(b, a, w);
            }

            // 暴力枚举前面的电梯有无j层停靠
            // 有停靠就60秒换乘
            for (int k = 1; k < i; k++)
                if (g[k][now]){              //第k个电梯也能到t层
                    int c = k * 100 + now;
                    add(c, b, 60); add(b, c, 60);
                }

            if (now == ed){
                add(b, super_ed, 0); add(super_ed, b, 0);     //建立一个超级终点(类似超级源点)
            }
        }
    }
}

void dijkstra(){
    memset(d, 0x3f, sizeof d);
    memset(vis, false, sizeof vis);

    d[0] = 0;
    priority_queue<PII> q;
    q.push(make_pair(0, 0));

    while (!q.empty()){
        PII t = q.top(); q.pop();
        int ver = t.second, dist = -t.first;

        if (vis[ver]) continue;
        vis[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i]){
            int j = e[i];
            if (dist + w[i] < d[j]){
                d[j] = dist + w[i];
                q.push(make_pair(-d[j], j));
            }
        }
    }
}

int getret(){
    int ret = INF;
    for (int i = 1; i <= n; i++){
        int p = i * 100 + ed;
        if (d[p] < ret) ret = d[p];
    }

    return ret;
}

int main(){
    while (cin >> n >> ed){
        init();
        build();
        dijkstra();

        int ret = d[super_ed];
        if (ret == INF) cout << "IMPOSSIBLE" << '\n';
        else cout << ret << '\n';
    }

    return 0;
}