UVa 10801

A.cpp

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <sstream>
#include <functional>
using namespace std;

#define MAX_VER 222
#define INFINITE 0x3FFFFFFF // ~ 1.000.000.000

struct edge {
    int to;
    int dist;
    edge(int to, int dist) : to(to), dist(dist) {}
};
struct vertex {
    vector<edge> edges;
    // minDist and previous are for Dijkstra and Bellman-Ford
    int minDist;
    int prev;
};

vertex vertices[MAX_VER];

void reset() {
    for (int i = 0; i < MAX_VER; i++) {
        vertices[i].edges.clear();
        vertices[i].minDist = INFINITE;
        vertices[i].prev = -1;
    }
}

void add_edge(int a, int b, int dist) {
    vertices[a].edges.push_back(edge(b, dist));
}

// #include <functional> for greater<pp>
typedef pair<int,int> pp;
typedef vector<edge>::iterator iter;
void dijkstra(int source) {
    priority_queue<pp,vector<pp>,greater<pp> > Q;
    vertices[source].minDist = 0;
    Q.push(make_pair(0, source));
    while (!Q.empty()) {
        pp u = Q.top();
        Q.pop();
        vertex vert = vertices[u.second];
        if (u.first > vert.minDist)
            continue;
        for (auto &e : vert.edges) {
            if (u.first + e.dist < vertices[e.to].minDist) {
                vertices[e.to].minDist = u.first + e.dist;
                vertices[e.to].prev = u.second;
                Q.push(make_pair(vertices[e.to].minDist, e.to));
            }
        }
    }
}
list<int> get_shortest_path(int target) {
    list<int> path;
    for (int vertex = target; vertex != -1; vertex = vertices[vertex].prev) {
        path.push_front(vertex);
    }
    return path;
}

int T[111];

void run(int n, int k)
{
    reset();
    for (int i = 0; i < n; i++)
        cin >> T[i];

    cin.ignore();

    for (int i = 0; i < n; i++) {
        string line;
        getline(cin, line);
        stringstream str(line);
        vector<int> floors;
        int fl;
        while (str >> fl)
            floors.push_back(fl);

        for (auto &a : floors) {
            for (auto &b : floors) {
                if (a != b) {
                    add_edge(a + 105, b, (abs(a-b) * T[i]));
                }
            }
        }
    }

    // also add floor edges
    for (int i = 0; i < 100; i++)
        add_edge(i, i + 105, 60);

    dijkstra(105);

    if (vertices[k].minDist >= INFINITE)
        cout << "IMPOSSIBLE" << endl;
    else
        cout << vertices[k].minDist << endl;
}
int main()
{
    int n, k;
    while (cin >> n >> k)
        run(n, k);
}

A.in

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
2 99
100 1
0 1 98 99
1 98
3 1
100 10 100
0 1
0 1
0 1
1 1
100
1 2
2 5
1 1
0 3
4 5
4 89
7 2 4 8
3 34 45 56 77
4 23 34 89
0 99
3 99
5 99
12 90 34 56 22
0 4 7 3 6 8 98
4 10 20 23 46 50 69 88 99
0 3 12 45 50 77 88 99
0 20 46 77 98
0 50
2 99
10 40
1 2 3 4 99 0 12
3 4 2 0 12 99
2 2
10 5
0 1 2
1 2
3 2
100 5 3
0 1 2
1 2
1 2
3 2
100 5 3
0 1 2
0 1
1 2
3 30
100 100 1
0 2 4 5 6 7 8 21 22 23 24 25 26 30
1 2 19 11 12 13 14 15 16 30
1 10 30
2 99
100 1
0 1 98 99
1 98
3 1
100 10 100
0 1
0 1
0 1
2 5
1 1
0 3
4 5
4 89
7 2 4 8
3 34 45 56 77
4 23 34 89
0 99
3 99
5 99
12 90 34 56 22
0 4 7 3 6 8 98
4 10 20 23 46 50 69 88 99
0 3 12 45 50 77 88 99
0 20 46 77 98
0 50
2 99
10 40
1 2 3 4 99 0 12
3 4 2 0 12 99
2 2
10 5
0 1 2
1 2
3 2
100 5 3
0 1 2
1 2
1 2
3 2
100 5 3
0 1 2
0 1
1 2
2 90
1 10
0 80
80 90
2 99
100 1
0 1 98 99
1 98
3 5
100 1 1
0 5
0 10
5 10

A.out

275
285
3920
IMPOSSIBLE
417
10
IMPOSSIBLE
IMPOSSIBLE
1671
2826
990
20
163
68
449
417
10
IMPOSSIBLE
1671
2826
990
20
163
68
240
417
75