블로그 옮겼습니다

문제 링크 \(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