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