다익스트라 썸네일형 리스트형 BOJ) 10282 Failing Components 문제: icpc.me/10282 그래프가 주어지고 실패되는 A정점이 주어질 때 A정점에게 의존되는 모든 정점들이 실패되는데 이때 실패되는 정점 수와 실패가 전파되는 총 시간을 출력하는 문제이다. A정점부터 다익스트라를 실행하여 값이 갱신될 때 마다 시간의 최댓값을 갱신해주면서 개수를 세주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include #include #include #define MAX_N 10000using namespace std;int t, n, d, c, x, y, z, r, a;int dp[MAX_N + 1];priority_queuepq;int main(){.. 더보기 BOJ)2211 네트워크 복구 문제:icpc.me/2211 원본 네트워크가 주어질 때 1.최소 개수의 회선만 복구하면서 2. 1번 노드에서 k번 노드의 최단거리가 원본보다 길어지지 않도록 복구하라는 문제이다. 처음에 1번 조건만 봤을때는 MST를 떠올릴 수 있으나 2번조건 때문에 다익스트라를 이용하여 1번 정점부터 최단거리를 구해주면서 사용되는 모든 간선을 벡터에 저장해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include #include #include #define MAX_N 1000using namespace std;int n, m, a, b, c, dp[MAX_N + 1];priority_qu.. 더보기 BOJ)13913 숨바꼭질4 문제:icpc.me/13913 X의 위치에서 1초후에 X+1,X-1,2*X의 위치로 이동가능할 때 K로 가는데 걸리는 가장 빠른시간과 경로를 출력하는 문제이다. 우리는 각 좌표를 정점으로 생각하여 다익스트라를 돌린다면 가장 빠른시간을 구할 수 있다. 경로를 출력하는것은 백트래킹을 해야하는데 좌표N에 대한 최단경로가 갱신되는 순간에 N을 부른 위치를 기록해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include #include #include using namespace std;int dp[250000], n, k, back[250000];stack st;int main().. 더보기 BOJ)13549 숨바꼭질3 문제:icpc.me/13549 X의 위치에서 1초후에 X+1혹은 X-1로 이동가능하고 순간이동을 할경우 0초후에 2*X위치로 이동가능할 때 K까지 가는 가장 빠른 시간을 출력하는 문제이다. 각 좌표를 정점으로 생각하여 다익스트라를 돌리면 된다. 12345678910111213141516171819202122232425262728#include #include #include #include using namespace std;int dp[250000], n, k;int main() { scanf("%d%d", &n, &k); memset(dp, -1, sizeof(dp)); priority_queue pq; pq.push({ 0, n }); while (pq.size()) { int here = pq.t.. 더보기 BOJ)13911 집 구하기 문제: icpc.me/13911 맥세권과 스세권을 만족하는 집 중 최단거리의 합이 최소인 집을 구하면 된다. 맥도날드로 부터 거리를 구하기 위한 다익스트라와 스타벅스로 부터 거리를 구하기 위한 다익스트라를 두번 돌려 준 후 mdp[x]와 sdp[x]가 정해진 거리를 만족하면서(맥세권,스세권이면서) mdp[x]+sdp[x]가 최소인 거리를 출력해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include #include #include #include #include #define IN.. 더보기 BOJ 5719) 거의 최단 경로 문제: icpc.me/5719 BOJ 5719 다익스트라로 최단경로를 구현하고 최단경로에 포함되는 모든 간선들을 지워준 뒤 다시 다익스트라를 실행하면 된다. 최단경로에 속하는지 여부는 BFS처럼 처음에 queue에 도착지점을 넣어준 뒤 하나씩 빼면서 for(i 0~n-1) dp[here]= dp[i]+dist[i][here]를 만족하는 경우에 dist[i][here]를 지워주고 i를 큐에 삽입하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include #include #include using namespace std;int n, m, x.. 더보기 이전 1 2 다음