1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| #include <iostream>
#include <climits>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
using namespace std;
#define mp make_pair
#define pr pair<int,int>
#define INF 9999999
vector<vector<pair<int, int>>> edges;
vector<int> T;
priority_queue<pr, vector<pr>, greater<pr>>pq;
vector<int> dis;
void dijkstra() {
dis.assign(701, INF);
dis[0] = 0;
pq.emplace(mp(0, 0));
while (!pq.empty()) {
int x = pq.top().second;
int val = pq.top().first;
pq.pop();
for (auto y : edges[x]) {
if (dis[y.first] > dis[x] + y.second) {
dis[y.first] = dis[x] + y.second;
pq.push(mp(dis[y.first], y.first));
}
}
}
}
void connect(int x, int y, int cost) {
edges[x].emplace_back(mp(y, cost));
edges[y].emplace_back(mp(x, cost));
}
void print(int x) {
for (auto it : edges[x]) {
cout << it.first << " " << it.second << endl;
}
}
int main() {
int n, k;
while (cin >> n >> k) {
T.assign(n + 1, 0);
edges.assign(701, vector<pair<int, int>>());
for (int i = 1; i <= n; i++)
cin >> T[i];
cin.ignore();
for (int i = 1; i <= n; i++) {
string s;
getline(cin, s);
stringstream ss(s);
int x, y;
ss >> x;
if (x == 0)
connect(0, 100 * i, 0);
while (ss >> y) {
connect(100 * i + x, 100 * i + y, (y - x) * T[i]);
x = y;
}
}
for (int i = 0; i < 100; i++)
for (int x = 1; x <= n; x++)
for (int y = x + 1; y <= n; y++)
if (!edges[x * 100 + i].empty() && !edges[y * 100 + i].empty())
connect(x * 100 + i, y * 100 + i, 60);
for (int x = 1; x <= n; x++)
if (!edges[x * 100 + k].empty())
connect(x * 100 + k, 700, 0);
dijkstra();
if (dis[700] == INF)
cout << "IMPOSSIBLE\n";
else cout << dis[700] << endl;
}
}
|