목록데이크스트라 (8)
정화 코딩
[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++] 파티 (백준 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 4회차 정모 (다익스트라 / 벨만-포드)
A. 지름길 (백준 1446번) https://www.acmicpc.net/problem/1446 #pythonfrom sys import stdinimport sysfrom queue import PriorityQueuen, 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..
EDOC 2023-W 1회차 과제 (그래프의 표현)
08-1. 그래프의 표현 046. 특정 거리의 도시 찾기 (백준 18352번) https://www.acmicpc.net/problem/18352 from sys import stdin from collections import deque n, m, k, x = map(int, stdin.readline().split()) g = [[] for _ in range(n+1)] visited = [-1] * (n+1) ans = [] def bfs(v): que = deque() que.append(v) visited[v] += 1 while que: new = que.popleft() for x in g[new]: if visited[x] == -1: que.append(x) visited[x] = vis..