목록최단 경로 (11)
정화 코딩
[C++] 서강그라운드 (백준 14938번)
https://www.acmicpc.net/problem/14938 우선 모든 노드와 노드 사이의 최단 경로를 구해 놓는다.그 후 각 지역에 떨어졌다고 가정했을 때, 얻을 수 있는 아이템의 수를 구해서 최댓값을 찾는다. 모든 노드 간의 최단 경로가 필요하기 때문에 플로이드-워셜을 사용하였다. #include #include using namespace std;int MAX_SIZE = 1000000000;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m, r; cin >> n >> m >> r; vector item(n + 1); for (int i = 1; i > item[i];..
[C++] 최소비용 구하기 2 (백준 11779번)
https://www.acmicpc.net/problem/11779 #include #include #include using namespace std;int MAX_SIZE = 1000000000;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector>> g(n + 1); vector dst(n + 1, MAX_SIZE); vector route(n + 1); for (int i = 0; i > a >> b >> c; g[a].emplace_back(b, c); } int s, e; cin >> s >> ..
[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, ..