https://www.acmicpc.net/problem/1162 백준 1162번 도로포장 문제에요! 각 지점에서 도로를 몇번포장했는지 각각 다 체크해주어야하기 때문에 visited배열을 [정점수][포장사용한횟수]로 만들어줘야해요. 마지막에는 visited[정점수]에서 최솟값을 찾아주면 됩니다. *paved를 사용하면 paved++, 그냥이동(비용0) 사용하지않으면 기존의 다익스트라 알고리즘사용. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#include #include #include #include using names..
백준 5214:환승
https://www.acmicpc.net/problem/5214 백준 5214번 문제 환승이예요. 지금까지 풀었던 다익스트라 문제와는 많이 다른문제입니다. 정점끼리도 이어져있고, 하이퍼튜브끼리도 이어져있습니다. 이번문제의 쉬운 풀이법은! 기존의 문제대로 정점끼리 계산을 하되 하이퍼튜브도 정점으로 생각해서 계산해 주는것. 정점 + 하이퍼튜브로 계산하면 기존 다익스트라 문제와 비슷하게 풀 수 있어요! *참고한 블로그 http://degurii.tistory.com/19 이렇게 보시면 1 -> T1 -> 3 -> T3 -> 6 ->T5 -> 9 인 경우와 1 -> T2 -> 5 -> T4 -> 6 ->T5 -> 9 인 경우가 있어요!물론 T1 = N, T2 = N+1 .. 로 매칭된 정점을 이용하겠죠? 튜브..
https://www.acmicpc.net/problem/6118 이번문제는 간단한 다익스트라 알고리즘문제예요. 문제는 최단거리를 계산하지만! 가장먼곳(최장거리)를 계산하면 되는것이에요. 가장 작은번호 출력 주의! 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include #include #include using namespace std; #define INF (static_cast(1e9))#define endl '\n'typedef pair PAIR;int main(void) { ios::sync_with_stdio(false); int N, M; ci..
https://www.acmicpc.net/problem/13424 백준 13424번 비밀 모임이예요. 해리포터 보고싶다 이번 문제는 모든 친구들로부터 가장 짧은 곳을 찾아야하기때문에 각 테스트케이스마다 K번씩 탐색해야해요. 그래서 minimum배열에 각점에 대한 최단경로 정보들을 저장해 두고 마지막에 친구들이 가장 편하게? 올수 있는 방을 골라주면 됩니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include #include #include #include using namespace..
https://www.acmicpc.net/problem/2211 백준 2211번 다익스트라 관련 문제예요. 기본 최소비용탐색 문제에서 회선 정보만 빼오면 되는거예여. prev배열을 만들어서 현재노드와 전 노드를 연결하는 회선 정보를 저장해요. -1이라면 회선이 없는 것. 갯수를 카운팅 해주고 회선 정보를 출력하면 되요. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include #include #include using namespace std; #define INF (static_cast(1e9))#define endl '\n' typede..
https://www.acmicpc.net/problem/14618 백준 14618번 다익스트라 문제입니다. 다른 기본 문제들과 같이 시작점에서 (J점에서) 가장 가까운 점을 찾..으면 안되구요(경험담). A, B로 가는 가장 가까운 길을 찾아야합니다.. 그리고 A, B최단거리길이가 같으면 A를 출력하는 것도 고려해서.. 쿨럭ㅠㅠ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include #include #include #include using namespace std; #define INF (sta..
https://www.acmicpc.net/problem/1261 다익스트라 배열버전이예요.. 배열을 상하좌우로 연결된 그래프라고 보면 편해요. 배열을 다익스트라로 탐색하면되요. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include #include using namespace std;#define endl '\n'#define r first#define c secondconst char dr[4] = { 0,1,0,-1 };const char dc[4] = { -1,0,1,0 }; typedef pair pos;typedef pair PAIR;..
https://www.acmicpc.net/problem/4485 아니요.. 링크라구요 링크!!!...이번문제도.. 다익스트라 문제예요.. 하지만 입력에서는 배열이네요? 그러면 상하좌우로 연결된 그래프라고 생각하면 편합니다아.. 큐에는 좌표가 들어갑니다. (0, 0)에서 (N-1, N-1)까지 최소로 갈 수있는 합을 구하면됩니다.. 그리구 시작비용이 0이아니라! (0, 0)에 있는 값이 되겠네요. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include #include using namespace std;#defin..
이번문제는 다익스트라 문제예요.. 하지만 주어진 두점을 지나야 해요! 제가 생각한 풀이법은 이렇습니다.1. 두 점중에서 시작점과 가까운 거리를 구합니다!2. 두 점중에서 도착점과 가까운 거리를 구합니다!3. 두 점의 거리를 더해줍니다. *그리고 만약 첫번째 점을 시작점과 연결했다면 끝나는 점은 다른 한점과 연결해야 최소비용으로 지나갈 수 있겠죠? 교차해서 지나가야 한번씩 방문하면서 최소비용이 나와요! ->이렇게하면 '시작점 ~ (두 점중 택1) ~ (나머지 점) ~ 도착점'의 최단거리가 나올 것 같아요!그러므로 주어진 두 점에서 다익스트라알고리즘을 돌리면 최단거리가 나오겠죠? 123456789101112131415161718192021222324252627282930313233343536373839404..
https://www.acmicpc.net/problem/11066 dp제는 너무 어려운거 같아요. 바텀업보다 탑다운이 코드짜기 편하고해서 점화식만 잘세우고, 탈출조건만 잘짜면 된다하는데 아직 많이 어렵네요.. 밑에 코드에서는 start~end 까지 보는데 for문을 돌면서 start ~ i의 최소합 i+1 ~ end까지의 최소합을 구해서 리턴하면 되네요. sum배열은 누적합을 저장해놓은 배열이예요. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include #include using namespace std; int K;vector file;vector sum;vector dp; unsigne..