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