
출발, 도착 지점과 대포들이 놓인 지점들을 정점으로 두고 각 정점들 사이의 이동시간을 가중치로 두면, 일반적인 최소 비용 문제(최단 경로 문제)가 된다. 대포를 이용해서 이동하거나 도보로 가거나 두 가지 선택지 있다. 위의 정보로부터 대포의 위치가 아닌 시작 정점을 제외한 정점에서 다른 정점을 잇는 간선의 가중치는

문제 링크 : https://www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 어떤 지점을 중심으로 가장 가까운 맥도날드나 스타벅스를 구하라면 평범한 최단 경로 문제이겠으나, 정점들 중 거리의 합이 최소가 되어야 하므로 각 정점에서 맥도날드 스타벅스까지의 최단 경로를 구하기는 곤란하다. (정점이 너무 많다.) 그래서 출발 정점을 맥도날드나 스타벅스로 두고 해결해야 할 듯하다. (이것도 많은데?) 가장 가까운..
- Total
- Today
- Yesterday
- bash script
- stack
- persistent segment tree
- dynamic programming
- fenwick tree
- Reference
- Shell Programming
- number theory
- 백준
- 다익스트라
- Dijkstra
- shell
- segment tree
- Vim
- Aho-Corasick
- python3
- RUBY
- 세그먼트 트리
- BOJ
- lazy propagation
- javascript array
- math font
- 정수론
- script
- nearest common ancestor
- max flow
- JavaScript
- bash
- map
- C++ big number
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |