fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <list>
  5. #include <ctime>
  6. #include <algorithm>
  7. using namespace std;
  8.  
  9. enum class _error : int { shut_down, ValueErrorInt, ValueErrorChar, UnknownError };
  10.  
  11. // C++ 에러 메시지 참고 : https://learn.microsoft.com/ko-kr/cpp/error-messages/compiler-errors-1/c-cpp-build-errors?view=msvc-170
  12. void error(_error code, string message = "") {
  13. 	if (!message.empty())
  14. 		cout << "error: " << message << "\n";
  15.  
  16. 	switch (code) {
  17. 	case _error::shut_down:
  18. 		cout << "프로그램 비정상 종료\n";
  19. 		break;
  20. 	case _error::ValueErrorInt: // 잘못된 입력 - int
  21. 		cout << "ValueErrorInt: int 값이 입력되어야 합니다.\n";
  22. 		break;
  23. 	case _error::ValueErrorChar: // 잘못된 입력 - char
  24. 		cout << "ValueErrorChar: char 값이 입력되어야 합니다.\n";
  25. 		break;
  26. 	default:
  27. 		cout << "UnknownError: 알 수 없는 오류\n";
  28. 	}
  29.  
  30. 	exit(1); // 프로그램 비정상 종료
  31. }
  32.  
  33. struct cmp { // 다익스트라 우선순위 큐 비교 연산자 : 가중치가 적고 정점 번호가 적은 것을 우선으로 함
  34. 	bool operator()(pair<unsigned, unsigned> a, pair<unsigned, unsigned> b) {
  35. 		if (a.second == b.second)
  36. 			return a.first >= b.first;
  37. 		else
  38. 			return a.second > b.second;
  39. 	}
  40. };
  41.  
  42. template <typename T>
  43. struct Edge {
  44. 	T w; // 가중치
  45. 	unsigned from; // 시작점
  46. 	unsigned to; // 종점
  47. };
  48.  
  49. template <typename T>
  50. class TGraph {
  51. private:
  52. 	unsigned v; // 정점 수
  53. 	vector<Edge<T>> edges; // 그래프가 갖는 간선들
  54.  
  55. public:
  56. 	// 생성자
  57. 	TGraph() { this->v = 0; }
  58. 	TGraph(unsigned v) { this->v = v; }
  59.  
  60. 	// 함수 정의에 쓰인 const : 이 함수 안에서 쓰는 값들을 변경할 수 없다
  61. 	unsigned size() const { return v; } // 그래프가 갖는 정점의 수를 반환
  62. 	auto& edges_from() const { return this->edges; } // 그래프가 갖는 간선들을 반환
  63. 	// 특정 정점에 연결된 간선들만 반환
  64. 	auto edges_from(unsigned i) const { // 여기에 & 쓰면 결과가 제대로 반환이 안 됨. 근데 이유는 모름..
  65. 		vector<Edge<T>> edge_from_i;
  66. 		for (auto& e : edges) {
  67. 			if (e.from == i)
  68. 				edge_from_i.push_back(e);
  69. 		}
  70. 		/* // 이쪽 코드도 똑같은 기능을 함
  71. 		for (int idx = 0; idx < this->edges.size(); idx++) {
  72. 			if (this->edges[idx].from == i)
  73. 				edge_from_i.push_back(edges[idx]);
  74. 		}*/
  75. 		return edge_from_i;
  76. 	}
  77.  
  78. 	void add(Edge<T>&& e) { // 방향 간선 추가
  79. 		if (e.from > 0 && e.from <= this->v && e.to > 0 && e.to <= this->v)
  80. 			this->edges.push_back(e);
  81. 		else
  82. 			error(_error::shut_down, "정점 범위 초과");
  83.  
  84. 		return;
  85. 	}
  86.  
  87. 	void add_undir(Edge<T>&& e) { // 무방향 간선 추가
  88. 		if (e.from > 0 && e.from <= this->v && e.to > 0 && e.to <= this->v) {
  89. 			this->edges.push_back(e);
  90. 			this->edges.push_back(Edge<T>{e.w, e.to, e.from});
  91. 		}
  92. 		else
  93. 			error(_error::shut_down, "정점 범위 초과");
  94.  
  95. 		return;
  96. 	}
  97.  
  98. 	void print() { // 그래프 출력
  99. 		for (int i = 1; i <= v; i++) {
  100. 			cout << "# " << i << " : "; // 정점 번호
  101. 			vector<Edge<T>> edge = this->TGraph::edges_from(i); // 정점에 연결된 간선 가져오기
  102. 			for (auto& e : edge)
  103. 				cout << "(" << e.to << ", " << e.w << ")  "; // 정점에 연결된 간선 출력
  104. 			cout << "\n";
  105. 		}
  106. 		return;
  107. 	}
  108.  
  109. 	// 기본 : 시작점으로부터의 최소 거리만 구하는 다익스트라
  110. 	vector<unsigned> dijkstra(unsigned s) { // s는 시작점
  111. 		vector<unsigned> d(v + 1, numeric_limits<unsigned>::max()); // 저장용 거리 벡터. 정점 번호가 1부터 시작함
  112. 		vector<bool> visited(v + 1, false); // 방문 여부 초기화
  113. 		unsigned vert = s; // 이제 방문할 정점 : 아직 시작하지 않았으므로 시작점으로 초기화
  114. 		visited[0] = true; // 안 쓰는 인덱스 방문할 일 없게 미리 표시
  115. 		/*
  116. 		1. 시작점 방문
  117. 		2. 거리 파악
  118. 		3. 가장 가까운 곳으로 이동
  119. 		4. 반복
  120. 		*/
  121. 		d[s] = 0; // 시작점은 거리 0
  122.  
  123. 		while (find(visited.begin(), visited.end(), false) != visited.end()) { // 아직 방문하지 않은 정점이 남아있는 동안
  124. 			priority_queue<pair<unsigned, unsigned>, vector<pair<unsigned, unsigned>>, cmp> next_visit; // 다음에 방문할 정점 : (정점, 거리)
  125.  
  126. 			visited[vert] = true; // 정점 방문
  127. 			vector<Edge<T>> v_edge = edges_from(vert); // 지금 방문한 정점에 연결된 간선들 가져오기
  128.  
  129. 			for (auto& e : v_edge)
  130. 				d[e.to] = min(d[e.to], d[vert] + e.w); // 거리 업데이트
  131.  
  132. 			for (unsigned i = 1; i <= v; i++)
  133. 				next_visit.push(make_pair(i, d[i])); // 모든 간선을 우선순위 큐에 추가
  134.  
  135. 			while (!next_visit.empty()) { // 다음 방문 정점 고르기
  136. 				pair<unsigned, unsigned> next = next_visit.top(); // (정점, 거리)
  137. 				next_visit.pop();
  138. 				if (!visited[next.first]) { // 방문하지 않은 정점을 다음 방문지로 정하고 break
  139. 					vert = next.first;
  140. 					break;
  141. 				}
  142. 			}
  143. 		}
  144.  
  145. 		return d; // 거리 벡터 반환
  146. 	}
  147.  
  148. 	// 응용 : 다익스트라 경로 탐색
  149. 	vector<pair<unsigned, unsigned>> dijkstra_path(unsigned s) { // s는 시작점
  150. 		vector<pair<unsigned, unsigned>> d(v + 1, make_pair(numeric_limits<unsigned>::max(), s)); // 저장용 거리 벡터. 정점 번호가 1부터 시작함. (최소 비용 거리, 직전 경로 정점)
  151. 		vector<bool> visited(v + 1, false); // 방문 여부 초기화
  152. 		unsigned vert = s; // 이제 방문할 정점 : 아직 시작하지 않았으므로 시작점으로 초기화
  153. 		visited[0] = true; // 안 쓰는 인덱스 방문할 일 없게 미리 표시
  154. 		d[s].first = 0; // 시작점은 거리 0
  155.  
  156. 		while (find(visited.begin(), visited.end(), false) != visited.end()) { // 아직 방문하지 않은 정점이 남아있는 동안
  157. 			priority_queue<pair<unsigned, unsigned>, vector<pair<unsigned, unsigned>>, cmp> next_visit; // 다음에 방문할 정점 : (정점, 거리)
  158.  
  159. 			visited[vert] = true; // 정점 방문
  160. 			vector<Edge<T>> v_edge = edges_from(vert); // 정점에 연결된 간선 가져오기
  161.  
  162. 			for (auto& e : v_edge) {
  163. 				if (d[vert].first + e.w < d[e.to].first) { // 거리를 업데이트할 필요가 있을 때에만
  164. 					d[e.to].first = d[vert].first + e.w; // 거리 업데이트
  165. 					d[e.to].second = vert; // 직전 방문 정점 업데이트
  166. 				}
  167. 			}
  168.  
  169. 			for (unsigned i = 1; i <= v; i++)
  170. 				next_visit.push(make_pair(i, d[i].first)); // 모든 간선을 우선순위 큐에 추가
  171.  
  172. 			while (!next_visit.empty()) { // 다음 방문 정점 고르기
  173. 				pair<unsigned, unsigned> next = next_visit.top(); // (정점, 거리)
  174. 				next_visit.pop();
  175. 				if (!visited[next.first]) { // 방문하지 않은 정점을 다음 방문지로 정하고 break
  176. 					vert = next.first;
  177. 					break;
  178. 				}
  179. 			}
  180. 		}
  181.  
  182. 		return d;
  183. 	}
  184.  
  185. 	// 응용 : 다익스트라 경로 탐색 - 모든 경로 표시
  186. 	vector<pair<unsigned, list<unsigned>>> dijkstra_fullpath(unsigned s) { // s는 시작점
  187. 		vector<pair<unsigned, unsigned>> d(v + 1, make_pair(numeric_limits<unsigned>::max(), s)); // 저장용 거리 벡터. 정점 번호가 1부터 시작함. (최소 비용 거리, 직전 경로 정점)
  188. 		vector<bool> visited(v + 1, false); // 방문 여부 초기화
  189. 		vector<pair<unsigned, list<unsigned>>> full_path(v + 1); // 모든 경로 표시 벡터 : (거리, 경로)
  190. 		unsigned vert = s; // 이제 방문할 정점 : 아직 시작하지 않았으므로 시작점으로 초기화
  191. 		visited[0] = true; // 안 쓰는 인덱스 방문할 일 없게 미리 표시
  192. 		d[s].first = 0; // 시작점은 거리 0
  193.  
  194. 		while (find(visited.begin(), visited.end(), false) != visited.end()) { // 아직 방문하지 않은 정점이 남아있는 동안
  195. 			priority_queue<pair<unsigned, unsigned>, vector<pair<unsigned, unsigned>>, cmp> next_visit; // 다음에 방문할 정점 : (정점, 거리)
  196.  
  197. 			visited[vert] = true; // 정점 방문
  198. 			vector<Edge<T>> v_edge = edges_from(vert); // 정점에 연결된 간선 가져오기
  199.  
  200. 			for (auto& e : v_edge) {
  201. 				if (d[vert].first + e.w < d[e.to].first) { // 거리를 업데이트할 필요가 있을 때에만
  202. 					d[e.to].first = d[vert].first + e.w; // 거리 업데이트
  203. 					d[e.to].second = vert; // 직전 방문 정점 업데이트
  204. 				}
  205. 			}
  206.  
  207. 			for (unsigned i = 1; i <= v; i++)
  208. 				next_visit.push(make_pair(i, d[i].first)); // 모든 간선을 우선순위 큐에 추가
  209.  
  210. 			while (!next_visit.empty()) { // 다음 방문 정점 고르기
  211. 				pair<unsigned, unsigned> next = next_visit.top(); // (정점, 거리)
  212. 				next_visit.pop();
  213. 				if (!visited[next.first]) { // 방문하지 않은 정점을 다음 방문지로 정하고 break
  214. 					vert = next.first;
  215. 					break;
  216. 				}
  217. 			}
  218. 		}
  219.  
  220. 		// 위에서 알아낸 최소 비용 거리와 직전 방문 정점을 이용해 모든 경로 찾기
  221. 		// 도착점인 i로부터 시작점인 s까지 거슬러 올라가는 방식으로 탐색
  222. 		for (unsigned i = 1; i <= v; i++) {
  223. 			unsigned dest = d[i].second; // 시작점 s에서 정점 i를 찾아가는 경로상에서, i를 방문하기 직전의 정점
  224. 			full_path[i].first = d[i].first; // s에서 i로 가는 최소 비용
  225. 			full_path[i].second.push_front(i); // 도착점 i 먼저 리스트에 추가
  226. 			while (dest != s) { // 시작점 s에 도달하면 종료
  227. 				full_path[i].second.push_front(dest); // 지금 방문하는 점을 경로 맨 앞에 추가
  228. 				dest = d[dest].second; // 시작점에서 지금 방문한 점으로 오기까지, 직전 방문 정점을 다음 방문지로 지정
  229. 			}
  230. 			if (i != s) // 위의 반복문은 시작점 s를 다음 방문지로 지정하면 종료되기 때문에 경로에 추가되지 않으므로, 현재 도착점이 시작점과 다르다면 경로에 추가해야 함
  231. 				full_path[i].second.push_front(s);
  232. 		}
  233.  
  234. 		return full_path;
  235. 	}
  236. };
  237.  
  238. int main()
  239. {
  240. 	// 빠른 입출력
  241. 	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  242.  
  243. 	int n, k;
  244. 	TGraph<int> grp;
  245.  
  246. 	cin >> n >> k;
  247.  
  248. 	grp = TGraph<int>(n);
  249.  
  250. 	for (int i = 0; i < k; i++) {
  251. 		int w;
  252. 		unsigned fr, to;
  253. 		cin >> fr >> to >> w;
  254. 		grp.add_undir(Edge<int>{w, fr, to});
  255. 	}
  256.  
  257. 	grp.print();
  258.  
  259. 	for (int i = 1; i <= grp.size(); i++) {
  260. 		auto d = grp.dijkstra(i);
  261. 		cout << "\n기본 다익스트라 시작점 : " << i << "\n";
  262. 		for (int e = 1; e <= grp.size(); e++) {
  263. 			cout << "# " << e << " : " << d[e] << "\n";
  264. 		}
  265. 	}
  266.  
  267. 	for (int i = 1; i <= grp.size(); i++) {
  268. 		auto d = grp.dijkstra_path(i);
  269. 		cout << "\n경로 다익스트라 : (최소 비용, 직전 방문 정점)\n시작점 : " << i << "\n";
  270. 		for (int e = 1; e <= grp.size(); e++) {
  271. 			cout << "# " << e << " : (" << d[e].first << ", " << d[e].second << ")\n";
  272. 		}
  273. 	}
  274.  
  275. 	for (int i = 1; i <= grp.size(); i++) {
  276. 		auto d = grp.dijkstra_fullpath(i);
  277. 		cout << "\n모든 경로 다익스트라(거리, 경로)\n시작점 : " << i << "\n";
  278. 		for (int e = 1; e <= grp.size(); e++) {
  279. 			cout << "# " << e << "(" << d[e].first << ")" << " : ";
  280. 			for (auto& p : d[e].second) {
  281. 				cout << p << "  ";
  282. 			}
  283. 			cout << "\n";
  284. 		}
  285. 	}
  286.  
  287. 	return 0;
  288. }
Success #stdin #stdout 0.01s 5552KB
comments (?)
stdin
copy 
7 12
1 2 7
1 5 3
1 6 10
2 3 4
2 4 10
2 5 2
2 6 6
3 4 2
4 5 11
4 6 9
4 7 4
5 7 5
stdout
copy 
# 1 : (2, 7)  (5, 3)  (6, 10)  
# 2 : (1, 7)  (3, 4)  (4, 10)  (5, 2)  (6, 6)  
# 3 : (2, 4)  (4, 2)  
# 4 : (2, 10)  (3, 2)  (5, 11)  (6, 9)  (7, 4)  
# 5 : (1, 3)  (2, 2)  (4, 11)  (7, 5)  
# 6 : (1, 10)  (2, 6)  (4, 9)  
# 7 : (4, 4)  (5, 5)  

기본 다익스트라 시작점 : 1
# 1 : 0
# 2 : 5
# 3 : 9
# 4 : 11
# 5 : 3
# 6 : 10
# 7 : 8

기본 다익스트라 시작점 : 2
# 1 : 5
# 2 : 0
# 3 : 4
# 4 : 6
# 5 : 2
# 6 : 6
# 7 : 7

기본 다익스트라 시작점 : 3
# 1 : 9
# 2 : 4
# 3 : 0
# 4 : 2
# 5 : 6
# 6 : 10
# 7 : 6

기본 다익스트라 시작점 : 4
# 1 : 11
# 2 : 6
# 3 : 2
# 4 : 0
# 5 : 8
# 6 : 9
# 7 : 4

기본 다익스트라 시작점 : 5
# 1 : 3
# 2 : 2
# 3 : 6
# 4 : 8
# 5 : 0
# 6 : 8
# 7 : 5

기본 다익스트라 시작점 : 6
# 1 : 10
# 2 : 6
# 3 : 10
# 4 : 9
# 5 : 8
# 6 : 0
# 7 : 13

기본 다익스트라 시작점 : 7
# 1 : 8
# 2 : 7
# 3 : 6
# 4 : 4
# 5 : 5
# 6 : 13
# 7 : 0

경로 다익스트라 : (최소 비용, 직전 방문 정점)
시작점 : 1
# 1 : (0, 1)
# 2 : (5, 5)
# 3 : (9, 2)
# 4 : (11, 3)
# 5 : (3, 1)
# 6 : (10, 1)
# 7 : (8, 5)

경로 다익스트라 : (최소 비용, 직전 방문 정점)
시작점 : 2
# 1 : (5, 5)
# 2 : (0, 2)
# 3 : (4, 2)
# 4 : (6, 3)
# 5 : (2, 2)
# 6 : (6, 2)
# 7 : (7, 5)

경로 다익스트라 : (최소 비용, 직전 방문 정점)
시작점 : 3
# 1 : (9, 5)
# 2 : (4, 3)
# 3 : (0, 3)
# 4 : (2, 3)
# 5 : (6, 2)
# 6 : (10, 2)
# 7 : (6, 4)

경로 다익스트라 : (최소 비용, 직전 방문 정점)
시작점 : 4
# 1 : (11, 5)
# 2 : (6, 3)
# 3 : (2, 4)
# 4 : (0, 4)
# 5 : (8, 2)
# 6 : (9, 4)
# 7 : (4, 4)

경로 다익스트라 : (최소 비용, 직전 방문 정점)
시작점 : 5
# 1 : (3, 5)
# 2 : (2, 5)
# 3 : (6, 2)
# 4 : (8, 3)
# 5 : (0, 5)
# 6 : (8, 2)
# 7 : (5, 5)

경로 다익스트라 : (최소 비용, 직전 방문 정점)
시작점 : 6
# 1 : (10, 6)
# 2 : (6, 6)
# 3 : (10, 2)
# 4 : (9, 6)
# 5 : (8, 2)
# 6 : (0, 6)
# 7 : (13, 5)

경로 다익스트라 : (최소 비용, 직전 방문 정점)
시작점 : 7
# 1 : (8, 5)
# 2 : (7, 5)
# 3 : (6, 4)
# 4 : (4, 7)
# 5 : (5, 7)
# 6 : (13, 4)
# 7 : (0, 7)

모든 경로 다익스트라(거리, 경로)
시작점 : 1
# 1(0) : 1  
# 2(5) : 1  5  2  
# 3(9) : 1  5  2  3  
# 4(11) : 1  5  2  3  4  
# 5(3) : 1  5  
# 6(10) : 1  6  
# 7(8) : 1  5  7  

모든 경로 다익스트라(거리, 경로)
시작점 : 2
# 1(5) : 2  5  1  
# 2(0) : 2  
# 3(4) : 2  3  
# 4(6) : 2  3  4  
# 5(2) : 2  5  
# 6(6) : 2  6  
# 7(7) : 2  5  7  

모든 경로 다익스트라(거리, 경로)
시작점 : 3
# 1(9) : 3  2  5  1  
# 2(4) : 3  2  
# 3(0) : 3  
# 4(2) : 3  4  
# 5(6) : 3  2  5  
# 6(10) : 3  2  6  
# 7(6) : 3  4  7  

모든 경로 다익스트라(거리, 경로)
시작점 : 4
# 1(11) : 4  3  2  5  1  
# 2(6) : 4  3  2  
# 3(2) : 4  3  
# 4(0) : 4  
# 5(8) : 4  3  2  5  
# 6(9) : 4  6  
# 7(4) : 4  7  

모든 경로 다익스트라(거리, 경로)
시작점 : 5
# 1(3) : 5  1  
# 2(2) : 5  2  
# 3(6) : 5  2  3  
# 4(8) : 5  2  3  4  
# 5(0) : 5  
# 6(8) : 5  2  6  
# 7(5) : 5  7  

모든 경로 다익스트라(거리, 경로)
시작점 : 6
# 1(10) : 6  1  
# 2(6) : 6  2  
# 3(10) : 6  2  3  
# 4(9) : 6  4  
# 5(8) : 6  2  5  
# 6(0) : 6  
# 7(13) : 6  2  5  7  

모든 경로 다익스트라(거리, 경로)
시작점 : 7
# 1(8) : 7  5  1  
# 2(7) : 7  5  2  
# 3(6) : 7  4  3  
# 4(4) : 7  4  
# 5(5) : 7  5  
# 6(13) : 7  4  6  
# 7(0) : 7
https://ideone.com/boz68k
language:
C++14 (gcc 8.3)
created:
2 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!