- Today
- 25
- Total
- 39,891
목록그래프 (4)
PS와 개발을 공부하자
문제 링크 \(2\leq{N}\leq{10^5}\)\(1\leq{M}\leq{2\cdot{10^5}}\)\(1\leq{c}\leq{10^9}\)노드의 개수 N, 엣지의 개수 M, 각 엣지에는 색 c 가 부여된다. 색은 정수로 주어진다. 엣지는 양방향이다.두 노드 사이에 엣지는 여러개 있을 수 있다.출발점은 1번노드, 도착점은 N번노드이다. 출발점에서 도착점까지 갈 때 지나는 통로의 색을 순서대로 적는다.출발점부터 도착점까지 최단경로로 갈 때의 색의..
문제 링크 \(1\leq{V}\leq{10^3}\)\(1\leq{E}\leq{V\cdot(V-1)/2}\)\(1\leq{T}\leq{10}\)도시의수 V와 검사해야 할 도로의 수 E가 주어지고, E개의 줄에 대해 도로가 잇는 두 도시 a b 가 주어진다.모든 두 도시 간에는 도로가 있으며, 각 도로를 지나는데 드는 시간은 T이다.도로를 검사하는 검사자가 주어진 E개의 도로를 모두 지나야 한다. 이 때 최소 시간을 구하는 문제이다.모든 엣지의 가중..
홀수 Degree를 가진 노드의 수는 짝수개이다!짝수 Degree를 가진 노드에 대한 성질은 따로 없다.. 짝수개일 수도 홀수개일 수도 있음
그래프 + dp 이다.N<=60, M<=60, R<=10^5, K<=1000N개의 노드가 있고 M개의 차가 있고 R개의 쿼리가 들어온다.각 M개의 차마다 인접행렬이 주어지는데 i,j 의 원소는 이 차를 탔을때 i번노드에서 j번 노드로 가는 데 걸리는 시간이다.각각의 쿼리는 출발지 S, 도착지 E, 차를 갈아탈 수 있는 최대 횟수 K 로 이루어진다.각각의 쿼리에 대해 S에서 E로 최대 K번 차를 갈아탈 수 있을 때의 최단 시간을 ..