목록최단 경로 (9)
정화 코딩
[C++] 특정한 최단 경로 (백준 1504번)
https://www.acmicpc.net/problem/1504 #include #include #include using namespace std;int INTMAX = 1000000;int n, e, v1, v2;vector>> edge;int dijkstra(int s, int e) { vector dst(n + 1, INTMAX); priority_queue> pq; dst[s] = 0; pq.emplace(0, s); while (!pq.empty()) { int cost = -pq.top().first; int cur = pq.top().second; pq.pop(); for (auto nxt: edge[cur]) ..
[C++] 숨바꼭질 3 (백준 13549번)
https://www.acmicpc.net/problem/13549 #include #include #include using namespace std;bool vst[300001];int dx[] = {1, -1};int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k; cin >> n >> k; queue> q; int cur, cnt; bool fin = false; q.emplace(n, 0); vst[n + 100000] = true; while (!fin) { cur = q.front().first; cnt = q.front()...
[C++] 웜홀 (백준 1865번)
https://www.acmicpc.net/problem/1865 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tc; cin >> tc; while (tc--) { int n, m, w; cin >> n >> m >> w; vector> edge; vector dst(n + 1, 100000000); int s, e, t; dst[1] = 0; for (int i = 0; i > s >> e >> t; edge.pus..
[C++] 파티 (백준 1238번)
https://www.acmicpc.net/problem/1238 #include #include using namespace std;int n, m, x;vector> g;int MAX = 1000000000;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> x; g = vector>(n + 1, vector(n + 1, MAX)); for (int i = 0; i > a >> b >> t; g[a][b] = t; } for (int k = 1; k 처음에는 다익스트라로 하려고 했는데, 어차피 사람당 갔다 왔다 이렇게 2번 해야 해서 총 2*n번..
EDOC 2023-W 5회차 정모 (플로이드-워셜 / 최소 신장 트리)
A. 호석이 두 마리 치킨 (백준 21278번) https://www.acmicpc.net/problem/21278 #python from sys import stdin import sys n, m = map(int, stdin.readline().split()) g = [[sys.maxsize for _ in range(n+1)] for _ in range(n+1)] for i in range(1, n+1): g[i][i] = 0 for _ in range(m): a, b = map(int, stdin.readline().split()) g[a][b] = 1 g[b][a] = 1 for i in range(1, n+1): # 경유지 i에 대해 for j in range(1, n+1): # 출발 노드 j..
EDOC 2023-W 4회차 과제 (플로이드-워셜 / 최소 신장 트리)
08-6. 플로이드-워셜 061. 플로이드 (백준 11404번) https://www.acmicpc.net/problem/11404 from sys import stdin import sys n = int(stdin.readline()) m = int(stdin.readline()) g = [[sys.maxsize for _ in range(n+1)] for _ in range(n+1)] for i in range(n+1): g[i][i] = 0 for _ in range(m): a, b, c = map(int, stdin.readline().split()) if c < g[a][b]: g[a][b] = c for i in range(1, n+1): # 경유지 i에 관해 for j in range(1, ..
EDOC 2023-W 4회차 정모 (다익스트라 / 벨만-포드)
A. 지름길 (백준 1446번) https://www.acmicpc.net/problem/1446 #python from sys import stdin import sys from queue import PriorityQueue n, d = map(int, stdin.readline().split()) g = [[] for _ in range(10001)] visited = [False] * (10001) dst = [sys.maxsize] * (10001) que = PriorityQueue() for i in range(d): g[i].append((i+1, 1)) for _ in range(n): a, b, c = map(int, stdin.readline().split()) g[a].append(..
EDOC 2023-W 3회차 과제 (다익스트라 / 벨만-포드)
08-4. 다익스트라 056. 최단경로 (백준 1753번) https://www.acmicpc.net/problem/1753 from sys import stdin from queue import PriorityQueue import sys v, e = map(int, stdin.readline().split()) g = [[] for _ in range(v+1)] dst = [sys.maxsize] * (v+1) visited = [False] * (v+1) que = PriorityQueue() start = int(stdin.readline()) dst[start] = 0 que.put((0, start)) for _ in range(e): a, b, c = map(int, stdin.readlin..