플로이드와샬3 [백준 11780]플로이드2 www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드를 사용하는 경로 역추적 문제이다. eazymean.tistory.com/384 [알고리즘] 최단 경로 역추적 다익스트라 알고리즘과 플로이드 와샬을 사용한 최단거리 찾기 문제에서 종종 출제되는 경로 역추적 문제이다. 최단 거리와 그 경로를 찾는 문제로 다익스트라 알고리즘과 플로이드 와샬의 역 eazymean.tistory.com 경로 cost를 long long까진 안했어도 됐던 것 같다. 플로이드는.. 2021. 4. 11. [백준 14588] Line Friends (Small) www.acmicpc.net/problem/14588 14588번: Line Friends (Small) Q개의 줄에 걸쳐 두 선분이 가까운 정도를 출력한다. 만약, 두 선분 사이의 친구 관계가 단절되었다면 -1을 출력한다. www.acmicpc.net #include #include #include #define MAX 1e9 using namespace std; struct s { int left, right; }; int n, l, r, q, a, b; s arr[301]; int dis[301][301]; bool check(int a, int b) { if (arr[a].right < arr[b].left || arr[b].right < arr[a].left) { return 0; } retur.. 2021. 1. 2. [알고리즘] Floyd-Warshall 알고리즘 모든 최단 거리를 구하는 방법 all pairs shortest path problem 그래프 종류: weighted, directed graph G = (V,E) 이때 weight func w: E->R (R은 실제 weight값, edge에 weight를 매핑한다.) 경로 p의 weight w(p)는 특징 1. 음의 가중치를 가진 간선 사용가능 (다익스트라는 음의 가중치 간선 불가) 2. 자료구조는 2차원 배열 사용 3. optimal substructure 개념 사용 4. 시간복잡도 O(V^3) *optimal substructure 최단 경로 p내에 있는 정점 사이의 path도 모두 최단 경로이다. -> dp사용 초기화 거리를 저장하는 배열 dis[i][j] = c : i에서 j까지 비용이 c 모.. 2020. 3. 13. 이전 1 다음
