fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<queue>
  4.  
  5. using namespace std;
  6. #define Inf 987654321
  7. int V, E, start;
  8. int dt[20001], visit[20001];
  9. vector<pair<int, int> > v[20001];
  10.  
  11. void func() {
  12. 	queue<int> q;
  13. 	q.push(start);
  14.  
  15. 	while (1) {
  16. 		int size = q.size();
  17.  
  18. 		if (size == 0)
  19. 			break;
  20.  
  21. 		int sv = q.front();
  22. 		q.pop();
  23.  
  24. 		for (int i = 0; i < v[sv].size(); i++) {
  25. 			if(visit[v[sv][i].first] == 0){
  26. 				visit[v[sv][i].first] = 1;
  27. 				if (dt[v[sv][i].first] > v[sv][i].second + dt[sv]) {
  28. 					dt[v[sv][i].first] = v[sv][i].second + dt[sv];
  29. 				}
  30. 				q.push(v[sv][i].first);
  31. 			}
  32. 			//한 점에서 두번째 방문시 길이 체크
  33. 			else if (visit[v[sv][i].first] == 1) {
  34. 				if (dt[v[sv][i].first] > v[sv][i].second + dt[sv]) {
  35. 					dt[v[sv][i].first] = v[sv][i].second + dt[sv];
  36. 				}
  37. 			}
  38.  
  39. 		}
  40.  
  41. 	}
  42.  
  43. }
  44.  
  45. int main() {
  46. 	scanf("%d %d", &V, &E);
  47. 	scanf("%d", &start);
  48.  
  49. 	for (int i = 0; i < E; i++) {
  50. 		int a, b, c;
  51. 		scanf("%d %d %d", &a, &b, &c);
  52. 		v[a].push_back(pair<int, int>(b, c));
  53.  
  54. 	}
  55.  
  56. 	for (int i = 1; i <= V; i++)
  57. 		dt[i] = Inf;
  58. 	dt[start] = 0;
  59. 	//func
  60. 	func();
  61.  
  62. 	for (int i = 1; i <= V; i++){
  63. 		if (dt[i] == Inf)
  64. 			printf("INF\n");
  65. 		else
  66. 			printf("%d\n", dt[i]);
  67. 	}
  68.  
  69.  
  70. 	return 0;
  71. }
Success #stdin #stdout 0s 15864KB
comments (?)
stdin
copy 
4 4
1
1 2 3
1 3 1
3 2 1
2 4 1
stdout
copy 
0
2
1
4
https://ideone.com/W945Yd
language:
C++14 (gcc 8.3)
created:
5 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!