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번노드이다. 출발점에서 도착점까지 갈 때 지나는 통로의 색을 순서대로 적는다.출발점부터 도착점까지 최단경로로 갈 때의 색의 sequence 를 구하는 문제. 만약 최단경로가 여러개라면사전순으로 앞서는 sequence 를 구하는 문제이다.우선 priority_queue 를 사용해 다익스트라를 하듯이 거리와 색의 우선순위에 따라 도착지까지 가면서색의 seqeunce 를 구해주면 될 거..

문제 링크 \(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개의 도로를 모두 지나야 한다. 이 때 최소 시간을 구하는 문제이다.모든 엣지의 가중치가 T로 같은 것이기 때문에 이 문제는 결국 최소의 간선을 지나면서 주어진 간선을 모두 지나는문제를 풀고 T를 곱하면 된다. 최소의 간선을 지나려면 주어진 간선들을 딱 한번씩만 지나고주어진 간선 외의 간선은 가능한한 지나지 않으면 될 것이다. 주어진 간선만을 한..

홀수 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번 차를 갈아탈 수 있을 때의 최단 시간을 답하면 된다.다익스트라 응용문제에서 처럼 현재 위치와 갈아탄 횟수와 현재 타고있는 차에 따라 노드를 더 세분화 하여 그래프를 만들어서 풀려고 했더니 노드의 수만 N*M*K, 즉 최악의 경우 360만개가 될 수 있다는 말이며, 엣지는 꽉 찬 그래프 이기때문에 엄청나게 많다..다익스트..