코딩캠프26 [11657] 타임머신 // 11657 타임머신 // 벨만포드 #include #include #include #include #define INF 987654321987654321 #define MAX_N 3000 using namespace std; struct Node { int start; int end; int cost; Node(int start, int end, int cost) : start(start), end(end), cost(cost) { } }; // 음수 오버플로우 주의 !!! // 500 * 6000 * -10000 은 음수 오버플로우 날 수 있음 long long dist[MAX_N]; vector adjList; // V : 정점의 수 // E : 간선의 수 // start : 시작 정점 bool.. 2024. 2. 20. [2458] 키 순서 // 2458 키 순서 #define INF 100 * 100000 + 1 #include #include #include #include using namespace std; int dist[501][501]; int N, M, a, b, c; // static 함수로 빼야 속도가 빠르다. // main 함수 내에 구현하지 말 것! void floyd() { // 꼭 k 를 가장 바깥쪽 for 루프에서 돌려야 정답이 나온다. 안쪽에 있으면 오답 for (int k = 1; k j 로 가는 거리가 더 짧다면 갱신한다. dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } } int main() { ios::sync_with_stdio(0); cin... 2024. 2. 20. [11404] 플로이드 // 11404 플로이드 #define INF 100 * 100000 + 1 #include #include #include #include using namespace std; int dist[101][101]; int N, M, a, b, c; // static 함수로 빼야 속도가 빠르다. // main 함수 내에 구현하지 말 것! void floyd() { // 꼭 k 를 가장 바깥쪽 for 루프에서 돌려야 정답이 나온다. 안쪽에 있으면 오답 for (int k = 1; k j 로 가는 거리가 더 짧다면 갱신한다. dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } } int main() { ios::sync_with_stdio(0); cin.. 2024. 2. 20. [1922] 네트워크 연결 // 1922 네트워크 연결 // MST : 프림 알고리즘 #include #include #include #include #include using namespace std; #define MAXV 100000 struct Node { int dest; int cost; Node(int dest, int cost) : dest(dest), cost(cost){ } // 디폴트가 최대힙이므로 최소힙으로 설정 ** bool operator a.cost; } }; int n, m; vector adjList[MAXV+1]; int V; // 정점 수 int E; // 간선의 수 priority_queue pq; // MST : 프림(Prim) 알고리즘 // 시작 정점 // 정점의 개수 V int prim(i.. 2024. 2. 20. [2252] 줄 세우기 // 2252 줄 세우기 // topology sort #include #define NMAX 32001 using namespace std; int N, M; int s, e; int visited[NMAX]; int inputEdgeCount[NMAX]; vector ordered; vector adj[NMAX]; void dfs(int u){ visited[u] = 1; for(int v: adj[u]){ if (visited[v] == 0) dfs(v); } // 목적지 -> 출발지 역순으로 들어감 ordered.push_back(u); } vector topologicalSort(int N){ // 초기화 ordered.clear(); memset(visited, 0, sizeof(visited.. 2024. 2. 19. [1717] 집합의 표현 // 1717 집합의 표현 // union find // 경로압축 -> 대표 루트로 업데이트해준다. #include #define NMAX 1000001 using namespace std; int n, m; int cmd, a, b; int parent[NMAX+1]; int getParent(int a){ if(parent[a] == a) return a; return parent[a] = getParent(parent[a]); // find 한 값을 배열에 저장 후 반환 //return getParent(parent[a]); } bool find(int a, int b){ // 같은 집합이면 true, 아니면 false int x = getParent(a); int y = getParent(b); .. 2024. 2. 19. 이전 1 2 3 4 5 다음