fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define int long long
  5. #define endl "\n"
  6.  
  7. void dij(int src, int dest, int n, vector<vector<pair<int,pair<int,int>>>> &adj, vector<int> &dist, int curr){
  8. 	priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> pq;
  9. 	pq.push({0, {src, curr}});
  10. 	dist[src] = 0;
  11. 	while (!pq.empty()) {
  12.         int u = pq.top().second.first;
  13.         int d = pq.top().first;
  14.         int cur = pq.top().second.second;
  15.         pq.pop();
  16.         if (u == dest) break;
  17.         if (d > dist[u]) continue;
  18.  
  19.         for(int i = 0; i < adj[u].size(); i++) {
  20.             int v = adj[u][i].first;
  21.             int weight = adj[u][i].second.first;
  22.             int cnt = adj[u][i].second.second;
  23.  
  24.             if(cnt != cur){
  25.             	weight += 60;
  26. 			}
  27.             if (dist[u] + weight < dist[v]) {
  28.                 dist[v] = dist[u] + weight;
  29.                 pq.push({dist[v], {v, cnt}});
  30.             }
  31.         }
  32.     }
  33. }
  34.  
  35. void splitnum(string s, int val, vector<vector<pair<int,pair<int,int>>>> &adj, int cnt, vector<int> &starter){
  36. 	stringstream ss(s);
  37. 	vector<int> floors;
  38. 	int num;
  39. 	while (ss >> num) {
  40. 		floors.push_back(num);
  41. 	}
  42. 	bool flag = true;
  43. 	for (int i = 1; i < floors.size(); i++) {
  44. 		int sum = val*(floors[i] - floors[i - 1]);
  45. 		adj[floors[i]].push_back({floors[i-1], {sum, cnt}});
  46. 		adj[floors[i-1]].push_back({floors[i], {sum, cnt}});
  47. 		if(floors[i - 1] == 0 && flag){
  48. 			starter.push_back(floors[i - 1]);
  49. 			flag = false;
  50. 		}
  51. 	}
  52. }
  53.  
  54. signed main(){
  55. 	ios_base::sync_with_stdio(0);
  56.     cin.tie(0);cout.tie(0);
  57.     int n, k;
  58.     while(cin >> n >> k){
  59.     	vector<int> elevator(n);
  60.     	vector<int> dist(100, LLONG_MAX);
  61.     	vector<vector<pair<int,pair<int,int>>>> adj(100);
  62.     	vector<int> starter;
  63.  
  64.     	for(int i = 0; i < n; i++){
  65.     		cin >> elevator[i];
  66. 		}
  67.  
  68.     	cin.ignore();
  69.     	for(int i = 0; i < n; i++){
  70.     		string s; 
  71.     		getline(cin, s);
  72.     		splitnum(s, elevator[i], adj, i, starter);
  73. 		}
  74.  
  75. 		dist[0] = 0;
  76. 		for(int i = 0; i < starter.size(); i++){
  77. 			dij(0,k,n,adj,dist,starter[i]);
  78. 		}
  79.  
  80. 		if (dist[k] == LLONG_MAX) {
  81. 			cout << "IMPOSSIBLE" << endl;
  82. 		} else {
  83. 			cout << dist[k] << endl;
  84. 		}
  85. 	}
  86. }
Success #stdin #stdout 0.01s 5296KB
comments ()
stdin
copy 
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
stdout
copy 
310
321
3920
IMPOSSIBLE
https://ideone.com/xwRtCt
language:
C++ (gcc 8.3)
created:
16 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!