fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define endl "\n"
  5.  
  6. struct Edge {
  7.     int from, to, cost, lid;
  8.     bool operator>(const Edge &e) const {
  9.         return cost > e.cost;
  10.     }
  11. };
  12.  
  13. signed main(){
  14.     ios_base::sync_with_stdio(0);
  15.     cin.tie(0); cout.tie(0);
  16.  
  17.     int n, k;
  18.     while (cin >> n >> k) {
  19.         vector<vector<Edge>> g(100);
  20.         vector<int> speed(n + 1);
  21.         for (int i = 1; i <= n; ++i) cin >> speed[i];
  22.  
  23.         cin.ignore();
  24.         for (int i = 1; i <= n; ++i) {
  25.             string s;
  26.             getline(cin, s);
  27.             stringstream ss(s);
  28.             vector<int> flrs;
  29.             int f;
  30.             while (ss >> f) flrs.push_back(f);
  31.  
  32.             for (int x = 0; x < flrs.size(); ++x) {
  33.                 for (int y = x + 1; y < flrs.size(); ++y) {
  34.                     int a = flrs[x], b = flrs[y];
  35.                     g[a].push_back({a, b, 0, i});
  36.                     g[b].push_back({b, a, 0, i});
  37.                 }
  38.             }
  39.         }
  40.  
  41.         vector<int> dist(100, -1), last(100, -1);
  42.         priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
  43.         pq.push({0, 0, 0, 0});
  44.         dist[0] = 0;
  45.  
  46.         while (!pq.empty()) {
  47.             Edge cur = pq.top(); pq.pop();
  48.             if (dist[cur.to] != cur.cost) continue;
  49.  
  50.             for (int i = 0; i < g[cur.to].size(); ++i) {
  51.                 Edge e = g[cur.to][i];
  52.                 int t = abs(e.to - e.from) * speed[e.lid];
  53.                 if (last[e.from] != -1 && last[e.from] != e.lid) t += 60;
  54.                 int newCost = dist[e.from] + t;
  55.                 if (dist[e.to] == -1 || newCost < dist[e.to]) {
  56.                     dist[e.to] = newCost;
  57.                     last[e.to] = e.lid;
  58.                     pq.push({e.from, e.to, newCost, e.lid});
  59.                 }
  60.             }
  61.         }
  62.  
  63.         if (dist[k] == -1) cout << "IMPOSSIBLE" << endl;
  64.         else cout << dist[k] << endl;
  65.     }
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0s 5272KB
comments (?)
stdin
copy 
3 14
12 34 35
0 12 23
8 14
9 12
3 14
3 2 1
0 14
0 14
0 14
3 14
3 2 1
0 1 2 3 4 5 6 7 8 9 14
12 13 14
9 14 
2 0
1 3
0 12
0 13
stdout
copy 
IMPOSSIBLE
14
42
0
https://ideone.com/Ax31bq
language:
C++ (gcc 8.3)
created:
14 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!