fork download
copy 
  1. // Priority Queue solution for Dijkstra's 
  2.  
  3. #include<bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. typedef pair<ll, ll> pi;
  9.  
  10. #define MP make_pair
  11. #define PB push_back
  12. #define F first
  13. #define S second
  14. #define MOD 1000000007
  15. #define INF 1e18
  16. #define N 10005
  17.  
  18. vector< vector<pi> > graph; // First is the vertex and Second is the weight
  19. bool vis[N];
  20. ll d[N];
  21.  
  22. void dijkstra(ll s) // s -> Source
  23. {
  24. 	fill(d, d + N, INF);
  25. 	memset(vis, false, sizeof vis);
  26. 	d[s] = 0;
  27. 	priority_queue< pi, vector<pi>, less<pi> > q;
  28. 	q.push(MP(d[s], s));
  29. 	while(!q.empty())
  30. 	{
  31. 		pi temp = q.top();
  32. 		q.pop();
  33. 		ll u = temp.S;
  34. 		//if(vis[u])
  35. 	//		continue;
  36. 	//	vis[u] = true;
  37. 		for(vector<pi> :: iterator it = graph[u].begin(); it != graph[u].end(); it++)
  38. 		{
  39. 			ll v = it -> F;
  40. 			ll wt = it -> S;
  41. 			if(d[v] > d[u] + wt)
  42. 			{
  43. 				d[v] = d[u] + wt;
  44. 				q.push( MP(d[v], v) );
  45. 			}
  46. 		}
  47. 	}
  48. }
  49.  
  50. int main()
  51. {
  52. 	ios::sync_with_stdio(false);
  53. 	ll t;
  54. 	ll n, m, a, b, w;
  55. 	ll i;
  56. 	cin >> t;
  57. 	while(t--)
  58. 	{
  59. 		cin >> n >> m;
  60. 		graph.clear();
  61. 		graph.resize(n + 2);
  62. 		for(i = 0; i < m; i++)
  63. 		{
  64. 			cin >> a >> b >> w;
  65. 			a--;
  66. 			b--;
  67. 			graph[a].PB(MP(b, w));
  68. 			// graph[b].PB({a, w});
  69. 		}
  70. 		cin >> a >> b;
  71. 		a--;
  72. 		b--;
  73. 		dijkstra(a);
  74. 		ll ans = d[b];
  75. 		if(ans == INF)
  76. 			cout << "NO" << endl;
  77. 		else
  78. 			cout << ans << endl;
  79. 	}
  80. 	return 0;
  81. }
  82.  
Success #stdin #stdout 0s 2960KB
comments (?)
stdin
copy 
3
3 2
1 2 5
2 3 7
1 3
3 3
1 2 4
1 3 7
2 3 1
1 3
3 1
1 2 4
1 3
stdout
copy 
12
5
NO
https://ideone.com/fIjPsL
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 years 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!