최단경로7 BOJ 1162 - 도로포장 (다익스트라) https://www.acmicpc.net/problem/1162 정점의 상태를 잘 정의하고 정의된 정점 간의 간선이 어떻게 이어져있는지를 잘 파악하면 된다. 양방향 가중치 그래프가 주어진다. 연결된 간선에 대해서 최대 k번 가중치를 0으로 만들 수 있을 때, 정점 1에서 정점n으로 가는 최단길이는? u번 정점 전까지 도로포장을 t번했다면 정점을 (u,t)로 정의한다 (정점의 상태가 최대 20개라서 가능) u->v에 대해 (u,t) -> (v,t), (v,t+1) .. t+1 다익스트라로 풀 수 있다. typedef pair P; typedef pair T; const int MAX = 1e4 + 2; const ll INF = 1e18; vector adj[MAX]; ll dist[MAX][21]; i.. 2020. 1. 25. codeforces #581 div2 C - Anna, Svyatoslav and Maps ( 플로이드 ) https://codeforces.com/contest/1204/problem/C 루프가 없는 단방향 그래프에 대해, 임의의 경로를 입력으로 주고, 그 입력의 처음과 끝은 그대로이지만 경로는 똑같을 수 밖에 없는 정점의 배열을 출력하는 문제. (물론 그 배열의 크기는 최소가 되도록.) 위와 같은 그래프와 입력이 1 2 3 4 1 2 3 4 일떄 출력은 1 2 4 2 4 이다. 1 3 4 2 4가 안되는 이유는 3번 정점을 방문하면 입력한 경로에서 벗어나기 때문이다. 풀이) 1. 첫번째 정점과 마지막 정점은 항상 출력해야 한다. 그리고 int arr[]에 입력 경로가 담겨있고, vector ans에 출력할 정답을 담는다고 하자. (pair엔 정점번호, 입력배열에서의 인덱스) 여기서 인덱스를 저장하는 것은 .. 2019. 11. 4. 벨만포드, SPFA 시작점을 정해줬을 때, 최단경로 알고리즘. 가중치가 음수여도 가능하다 *모든 간선을 돌면서 그에 속하는 정점에 대한 dist를 초기화할 수 있다면 초기화 해주는 작업을 정점개수-1만큼 반복한다. O(EV) 필요한 것: int dist[MAX]{0} vector adj[MAX]; //혹은 vector edge 일반적인 코드. 음의 사이클 검출방법 int main() { int N, M, dist[MAX], st, en; fill(dist, dist + N, INF); vector adj[MAX]; dist[st] = 0; bool minusCycle = false; for (int k = 0; k < N; k++) { // (N-1)번의 루프, N번째루프에 갱신되면 음의사이클존재 //이하 두개의 for문 .. 2019. 8. 18. 이전 1 2 다음
