본문 바로가기

Template4

Floyd-Warshall #include #include #define INF 1e9 #define NODES 101 using namespace std; int N, M; // 노드 간선 수 int dist[NODES][NODES]; int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin >> N >> M; for (int i = 1; i > v >> w; dist[u][v] = min(dist[u][v], w); } for (int k = 1; k 2020. 8. 15.
KMP from sys import stdin def input(): return stdin.readline().rstrip() def getFail(P): Plen=len(P) ret=[0]*Plen j=0 for i in range(1,Plen): while j>0 and P[i]!=P[j]: j=ret[j-1] if P[i]==P[j]: j+=1 ret[i]=j return ret def KMP(T, P): ret=[] Tlen=len(T) Plen=len(P) j=0 for i in range(Tlen): while j>0 and T[i]!=P[j]: j=fail[j-1] if T[i]==P[j]: if j==Plen-1: ret.append(str(i-Plen+2)) j=fail[j] else: j+=.. 2020. 8. 11.
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.
Tree #include using namespace std; typedef long long ll; const int MAX = 100001; int parent[MAX]; struct Tree { int root, size; vector child[MAX], edge[MAX]; Tree() { root = -1; size = 0; } Tree(int n) { root = -1; size = n; } void addEdge(int u, int v) { edge[u].push_back(v); edge[v].push_back(u); } void build(int id) { if (root == -1) root = id; for (int next : edge[id]) { if (!parent[next]) { pare.. 2020. 8. 6.