fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #define INF 99999999
  5. #define MAX_V 1001
  6. #define MAX_E 10001
  7. using namespace std;
  8.  
  9. int a, b, N, M;
  10. vector<pair<int, int>> adj[MAX_E];
  11. vector<int> dijkstra (int Value, int src)
  12. {
  13. 	vector<int> dist(Value+1, INF);
  14. 	dist[src] = 0;
  15. 	priority_queue<pair<int, int>> pq;
  16. 	pq.push(make_pair(0, src));
  17. 	while (!pq.empty())
  18. 	{
  19. 		int cost = -pq.top().first;
  20. 		int here = pq.top().second;
  21. 		pq.pop();
  22.  
  23. 		if (dist[here] < cost)	continue;
  24.  
  25. 		for (int i = 0; i < adj[here].size(); ++i)
  26. 		{
  27. 			int there = adj[here][i].first;
  28. 			int nextDist = cost + adj[here][i].second;
  29. 			if (dist[there] > nextDist)
  30. 			{
  31. 				dist[there] = nextDist;
  32. 				pq.push(make_pair(-nextDist, there));
  33. 			}
  34. 		}
  35. 	}
  36. 	return dist;
  37. }
  38. int main()
  39. {   
  40.     ios_base::sync_with_stdio(0);
  41.     cin.tie(0);
  42.     cout.tie(0);
  43.  
  44.     cin >> a >> b;
  45.     cin >> N >> M;
  46.  
  47.     for (int i = 0; i < M; ++i)
  48.     {
  49.         int u, v;
  50.         cin >> u >> v;
  51.         adj[u].push_back(make_pair(v, 1));
  52.         adj[v].push_back(make_pair(u, 1));
  53.     }
  54.  
  55.     vector<int> result = dijkstra(N, a);
  56.  
  57.     if (result[b] == INF)
  58.         cout << -1;
  59.     else
  60.         cout << result[b];
  61.  
  62.     return 0;
  63. }
Success #stdin #stdout 0s 5500KB
comments (?)
stdin
copy 
1 2
4 4
1 3
1 4
3 2
4 2
stdout
copy 
2
https://ideone.com/9nbq7N
language:
C++14 (gcc 8.3)
created:
3 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!