록키의 No Pain, No Gain

https://www.acmicpc.net/problem/1238 1238번: 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 www.acmicpc.net 다익스트라 문제.. 이 문제를 이전에는 인접 행렬로 풀었었는데 N = 1000이기 때문에 인접 행렬은 총 1,000,000개의 int 변수가 필요하다. 하지만 총 간선의 개수가 10000개 이하로 정해져있기 때문에 인접 행렬보다는 인접 리스트가 메모리상 효율적이고 시간복잡도 상에서도 더욱 효율적이다. 좀 더 최적화적인 관점에서 문제를 바라볼 필요가 있겠다. 그리고, C++은 기본적으로 우선순..

https://www.acmicpc.net/problem/1238 1238번: 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 www.acmicpc.net 플로이드 워셜이나 다익스트라 알고리즘을 사용하면 되는 문제 중요한건 다익스트라를 거꾸로 오는 경로로 생각했어야 했다. 그렇지 않으면 시간초과난다!!!!! #include #include #include #include #include #define INF 1000000 using namespace std; int N, M, X; int adj[1001][1001]; priority_queue..