목록데이크스트라 (6)
정화 코딩
[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 #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..
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..