본문 바로가기

라이브러리/그래프3

BFS #include using namespace std; typedef long long ll; typedef pair pii; int R, C; int board[100][100]; int dir8[2][8]{ {0, -1, 0, 1, -1, -1, 1, 1}, {1, 0, -1, 0, 1, -1, -1, 1} }; bool dup[100][100]; void bfs(pii init) { int cr, cc, nr, nc; queue que; dup[init.first][init.second] = true; for (que.push(init); !que.empty(); que.pop()) { tie(cr, cc) = que.front(); for (int i = 0; i < 4; ++i) { nr = cr.. 2020. 12. 13.
Topological Sort #include using namespace std; const int MAX = 10000 + 1; vector adj[MAX]; queue Q; int N, res; int indegree[MAX], cost[MAX], result[MAX]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; for (int i = 1; i > cost[i]; int K; cin >> K; for (int k = 1; k > p; adj[p].push_back(i); } if (indegree[i] == 0) { Q.push(i); result[i] = cost[i]; res = max(res, result[i]); } } for (int.. 2020. 9. 16.
Dijkstra struct Dijkstra { using elem = pair; const ll INF = 2e18; int vol; vector dup; vector adj; Dijkstra(int _vol) { vol = _vol + 1; dup.resize(vol, INF); adj.resize(vol); } void connect(int u, int v, ll w) { adj[u].push_back({w, v}); } void run(int base) { priority_queue que; que.push({0, base}); dup[base] = 0; while (!que.empty()) { auto [cw, id] = que.top(); que.pop(); if (dup[id] < cw) continue; .. 2020. 8. 6.

티스토리툴바