fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <queue>
  5. #include <stack>
  6. #include <algorithm>
  7. #include <cstdio>
  8. #include <map>
  9. #include <string>
  10.  
  11. using namespace std;
  12.  
  13. typedef pair<int, int> iPair;
  14.  
  15. vector<int> mapper;
  16. int p[11][11];
  17. vector<iPair> dist[250010];
  18. vector<iPair> ini[250010];
  19. int sdist[250010];
  20. bool visited[250010];
  21.  
  22. int main() {
  23. 	ios::sync_with_stdio(false);
  24. 	long long int n,m,k,s;
  25. 	cin>>n>>m>>k>>s;
  26. 	for(int i = 1; i <= k; i++) {
  27. 		for(int j = 1; j <= k; j++) {
  28. 			cin>>p[i][j];
  29. 		}
  30. 	}
  31. 	mapper.resize(n*10+10);
  32. 	//memset(sdist, 1e9, sizeof(long long int) * (n+2));
  33. 	int count = 1;
  34. 	int a,b,c,d,other,num,num1,first,second,so;
  35. 	for(int i = 0; i < m; i++) {
  36. 		cin>>a>>b>>c>>d;
  37. 		if(a == s || b == s) {
  38. 			so = s*10+1;
  39. 			if(mapper[so] == 0) {
  40. 				mapper[so] = count++;
  41. 			}
  42. 			other = (a==s) ? b*10+d:a*10+d;
  43. 			if(mapper[other] == 0) {
  44. 				mapper[other] = count++;
  45. 			}
  46. 			num = mapper[so], num1 = mapper[other];
  47. 			dist[num].push_back(make_pair(c, num1));
  48. 		} else {
  49. 			first = a*10+d;
  50. 			second = b*10 + d;
  51. 			if(mapper[first] == 0) {
  52. 				mapper[first] = count++;
  53. 			}
  54. 			if(mapper[second] == 0) {
  55. 				mapper[second] = count++;
  56. 			}
  57. 			num = mapper[first], num1 = mapper[second];
  58. 			ini[num].push_back(make_pair(c+p[d][d], num1));
  59. 			ini[num1].push_back(make_pair(c+p[d][d], num));
  60. 		}
  61. 	}
  62. 	for(int i = 1; i <= n; i++) {
  63. 		if(i!=s) {
  64. 			for(int j = 1; j <= k; j++) {
  65. 				if(mapper[i*10+j] != 0) {
  66. 					int num = mapper[i*10+j];
  67. 					for(int l = j; l <= k ; l++) {
  68. 						if(mapper[i*10 + l] != 0) {
  69. 							int num1 = mapper[i*10 + l];
  70. 							//cout<<num<<" "<<num1<<endl;
  71. 							//cout<<"i"<<i<<endl;
  72. 							//vector<iPair> temp;
  73. 							for(iPair pp : ini[num1]) {
  74. 								dist[num].push_back(make_pair(pp.first - p[l][l] + p[j][l], pp.second));
  75. 								//cout<<pp.first - p[l][l] + p[j][l]<<endl;
  76. 							}
  77. 							if(num != num1) {
  78. 								for(iPair pp : ini[num]) {
  79. 									dist[num1].push_back(make_pair(pp.first - p[j][j] + p[l][j], pp.second));
  80. 									//cout<<pp.first - p[j][j] + p[l][j]<<endl;
  81. 								}
  82. 							}
  83.  
  84. 						}
  85. 					}
  86. 					ini[num].clear();
  87. 				}
  88. 			}
  89. 		}
  90. 	}
  91. 	priority_queue< iPair, vector <iPair> , greater<iPair> > pq;
  92. 	int ss = mapper[s*10+1];
  93. 	for(int i = 1; i <= count; i++) {
  94. 		sdist[i] = (1<<31)-1;
  95. 	}
  96. 	sdist[ss] = 0;
  97. 	pq.push(make_pair(0,ss));
  98. 	while(!pq.empty()) {
  99. 		int u = pq.top().second;
  100. 		//cout<<"U:"<<u<<" "<<pq.top().first<<endl;
  101.         pq.pop();
  102.         if(!visited[u]) {
  103.         	visited[u] = true;
  104. 	        for(int i = 0; i<dist[u].size(); i++) {
  105. 	        	int dd = dist[u][i].first;
  106. 	        	int v = dist[u][i].second;
  107. 	        	//cout<<dd<<endl;
  108. 	        	/*if(dd==0) {
  109. 	        		cout<<"something"<<endl;
  110. 	        	}*/
  111. 	        	//cout<<"v:"<<v<<" "<<sdist[v]<<endl;
  112. 	        	if(sdist[v] > sdist[u]+dd) {
  113. 	        		//cout<<"something"<<endl;
  114. 	        		sdist[v] = sdist[u]+dd;
  115. 	        		pq.push(make_pair(sdist[v],v));
  116. 	        	}
  117. 	        }
  118.         }
  119.  
  120. 	}
  121. 	int temp;
  122. 	for(int i = 1; i <= n; i++) {
  123. 		int mini = (1<<31)-1;
  124. 		if(i!=s) {
  125. 			for(int j = 1; j <= k; j++) {
  126. 				temp = sdist[mapper[i*10+j]];
  127. 				if(temp!=0) {
  128. 					mini = min(temp, mini);
  129. 				}
  130. 			}
  131. 		}
  132. 		else {
  133. 			mini = 0;
  134. 		}
  135. 		if(mini == (1<<31)-1) {
  136. 			mini = -1;
  137. 		}
  138. 		cout<<mini<<" ";
  139. 	}
  140. 	cout<<endl;
  141.  
  142.  
  143.  
  144. }
  145.  
Time limit exceeded #stdin #stdout 5s 10552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/acPnqv
language:
C++14 (gcc 8.3)
created:
7 years 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!