fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. ll t;
  6.  
  7. queue<ll> nodeQueue;
  8.  
  9. void dijkstra(vector<vector<pair<bool, ll>>> &adjList, vector<pair<ll, ll>> &minDistance, vector<bool> &visited, ll curNode){
  10. 	if(visited[curNode]) return;
  11.  
  12. 	//cout << curNode << ' ';
  13.  
  14. 	visited[curNode] = true;
  15. 	for(auto i : adjList[curNode]){
  16. 		ll neighbour = i.second; 
  17. 		if(visited[neighbour]) continue;
  18.  
  19. 		nodeQueue.push(neighbour);
  20.  
  21. 		if(i.first){
  22. 			if(minDistance[neighbour].second==-1){
  23. 				minDistance[neighbour].second = minDistance[curNode].first+1;
  24. 				continue;
  25. 			}
  26. 			minDistance[neighbour].second = min(minDistance[neighbour].second, minDistance[neighbour].first+1);
  27. 		}
  28. 		else{
  29. 			minDistance[neighbour].first = min(minDistance[neighbour].first, minDistance[curNode].first+1);
  30. 			if(minDistance[curNode].second==-1) continue;
  31. 			if(minDistance[neighbour].second==-1){
  32. 				minDistance[neighbour].second = minDistance[curNode].second+1;
  33. 				continue;
  34. 			}
  35. 			minDistance[neighbour].second = min(minDistance[neighbour].second, minDistance[curNode].second+1);
  36. 		}
  37. 	}
  38.  
  39. 	while(!nodeQueue.empty()){
  40. 		ll neighbour = nodeQueue.front();
  41. 		nodeQueue.pop();
  42. 		dijkstra(adjList, minDistance, visited, neighbour);
  43. 	}
  44.  
  45. 	return;
  46. }
  47.  
  48. void solve(){
  49. 	ll node, road, toll, start, end;
  50. 	cin >> node >> road >> toll >> start >> end;
  51.  
  52. 	vector<vector<pair<bool, ll>>> adjList(node+1);
  53. 	//adjList[i].first==true	=> toll
  54. 	//					false	=> road;
  55. 	for(int i=1; i<=road; i++){
  56. 		ll a, b; cin >> a >> b;
  57. 		adjList[a].push_back({false, b});
  58. 		adjList[b].push_back({false, a});
  59. 	}
  60. 	for(int i=1; i<=toll; i++){
  61. 		ll a, b; cin >> a >> b;
  62. 		adjList[a].push_back({true, b});
  63. 		adjList[b].push_back({true, a});
  64. 	}
  65.  
  66. 	vector<pair<ll, ll>> minDistance(node+1, {LLONG_MAX, -1});
  67. 	//minDistance.first => minDistance without tolls
  68. 	//			 .second=> minDistance with tolls
  69. 	vector<bool> visited(node+1, false);
  70. 	minDistance[start].first = 0;
  71. 	dijkstra(adjList, minDistance, visited, start);
  72.  
  73. 	//for(auto i : minDistance) cout << i.first << ' ' << i.second << endl;
  74.  
  75. 	cout << min(minDistance[end].first, minDistance[end].second) << endl;
  76.  
  77. 	return;
  78. }
  79.  
  80. int main() {
  81. 	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  82. 	//cin >> t;
  83. 	t = 1;
  84. 	while(t--) solve();
  85. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
3 2 1 1 3
1 2
2 3
1 3
stdout
copy 
3
https://ideone.com/MbNiSZ
language:
C++14 (gcc 8.3)
created:
11 days ago
visibility:
secret

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!