fork(20) download
copy 
  1.  
  2.  
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <queue>
  7. #define N 123123
  8. #define M 5123
  9. using namespace std;
  10. int n, m;
  11. vector < vector<pair<int, int>>>G(N);
  12. vector<int>D(N, 1000000);//vinaxav pirvel umcires manzilebs
  13. vector<int>D2(N, 1000000);//vinaxav meore umcires manzilebs
  14. bool vis[N];
  15. priority_queue<pair<int, int>>Q;
  16. //long long total = 0;
  17. int f, s, t;
  18. int main(){
  19. 	scanf("%d %d", &n, &m);
  20. 	for (int i = 1; i <= m; i++){
  21. 		scanf("%d %d %d", &f, &s, &t);
  22. 		G[f].push_back(make_pair(s, t));
  23. 		G[s].push_back(make_pair(f, t));
  24. 	}
  25. 	D[1] = 0;
  26. 	Q.push(make_pair(-D[1], 1));
  27. 	while (!Q.empty()){
  28. 		int w = -Q.top().first;
  29. 		int a = Q.top().second;
  30. 		Q.pop();
  31. 		if (D2[a] < w)continue;
  32. 		for (int j = 0; j < G[a].size(); j++){
  33. 			int node = G[a][j].first;
  34. 			int weight = G[a][j].second;
  35. 			int d = weight + w;
  36. 			if (d< D[node]){//tu agmovachent rom ufro naklebi sigrzit mivdivart am wveroshi vidre vinaxavdit pirvel umcires wonianebshi  mashin pirveli umciresi sheicvleba axlit xolo meore if-shi ukve dzveli umciresi sigrze meore umciresi gza xdeba
  37. 				swap(d, D[node]);
  38. 				Q.push(make_pair(-D[node], node));
  39. 			}
  40. 			if (D2[node]>d){//
  41. 				D2[node] = d;
  42. 				Q.push(make_pair(-D2[node], node));
  43. 			}
  44. 		}
  45. 	}
  46. 	printf("%d", D2[n]);
  47. 	return 0;
  48. }
Success #stdin #stdout 0s 3596KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000
https://ideone.com/0FtdBa
language:
C++14 (gcc 8.3)
created:
8 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!