Wednesday, May 28, 2014

SRM 622

오랜만에 말려서 다 틀린 셋. Easy는 걍 말려서 헉헉 거리다가 결국 틀렸고 Medium은 몇 초를 남겨두고 다 짰는데 제출이 안됬다. 알고보니 아레나에서 컴파일을 안해서 제출이 안됬었음ㅠㅠ

Easy
두 정점 사이에 최단거리로 갈 때, 그 경로 상에 있는 간선들을 '사용'했다고 한다. 간선들이 T번 이상 사용된 걸 '불안'하다고 하는데 불안한 간선들의 가중치 합을 출력하시오.

플로이드로 풀릴 것 같아서 곧바로 짰는데 생각이 꼬여서 말리고 다익스트라로 급하게 짰다가 틀림ㅋㅋ 차근히 생각해보면 우선, 최단경로부터 다 구한 다음에 d[a][b] == d[a][i]+e[i][j]+d[j][b]인 e[i][j]를 카운팅해주면 됨. N<=50이라서 O(N^4)에도 너끈히 나온다.

Medium
그리디 알고리즘. 짤라내야하는 거 다 잘라내고 최대한 남겨둔 다음에 위로 올려서 재귀적으로 계산. 증명은 귀류법으로 됨.

Hard
안 읽어봤음.

No comments:

Post a Comment