운동

1. 링크드 리스트 2. 힙 사용 3. 음.. 내 코드로 만들어서 사용하기 4. 더블 링크드 리스트 5. 내 코드로 만들어서 사용하기....후....

1. 디피 2. 디피로 문제 풀 수 있는 유형 존재 3. 유형 파악 가능함 4. 오케잉.

#include <stdio.h> #include <stdlib.h> #define swap(a,b) {tmp = a; a = b; b=tmp;} struct line { int next, cost; }typedef Line; struct line_list { int count; Line next[400]; }typedef LL; struct heap_data { int num, dist; }typedef HD; LL lines[401]; int dist[401], check[401], heap_count; HD heap[20000], tmp; void Heapup(int n) { if (n > 1 && heap[n].dist < heap[n / 2].dist) { swap(heap[n], heap[n / 2]); Heapup(n / 2); } } void Push(int num, int dist) { heap_count++; heap[heap_count].num = num; heap[heap_count].dist = dist; Heapup(heap_count); } void Heapdown(int n) { int n1 = 2 * n, n2 = n1 + 1, min_n = n; if (n1 <= heap_count && heap[n1].dist < heap[min_n].dist) min_n = n1; if (n2 <= heap_count && heap[n2].dist < heap[min_n].dist) min_n = n2; if (min_n != n) { swap(heap[n], heap[min_n]); Heapdown(min_n); } } int Pop(void) { swap(heap[1], heap[heap_count]); heap_count--; Heapdown(1); return heap[heap_count + 1].num; } void AddLine(LL* list, int index, int next, int cost) { list[index].next[list[index].count].next = next; list[index].next[list[index].count].cost = cost; list[index].count++; } int main(void) { freopen("input.txt", "r", stdin); int t = 0; int tc = 0; int n, m, min_cycle; scanf("%d", &t); while (tc++ < t) { min_cycle = 1e9; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { lines[i].count = 0; } for (int i = 0, u, v, c; i < m; i++) { scanf("%d%d%d", &u, &v, &c); AddLine(lines, u, v, c); } for (int i = 1, j, k, u, v, c, r; i <= n; i++) { for (j = 1; j <= n; j++) { dist[j] = 1e9; check[j] = 0; } r = 1e9; heap_count = 0; dist[i] = 0; Push(i, 0); while (heap_count) { u = Pop(); if (check[u]) continue; if (dist[u] >= r) break; check[u] = 1; for (k = 0; k < lines[u].count; k++) { v = lines[u].next[k].next; c = lines[u].next[k].cost; if (v == i) { if (r > dist[u] + c) { r = dist[u] + c; } } else if (dist[v] > dist[u] + c) { dist[v] = dist[u] + c; Push(v, dist[v]); } } } if (r < min_cycle) { min_cycle = r; } } printf("#%d %d\n", tc, min_cycle); } }

#include <iostream> #include <algorithm> #define max_val 4000001 #define max_int 10 using namespace std; int t, n, m, a, b, c; int d[max_int][max_int]; int main() { freopen("input.txt", "r", stdin); scanf("%d", &t); for (int test_case = 1; test_case <= t; ++test_case) { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { d[i][j] = max_val; } } for (int i = 0; i < m; i++) { scanf("%d %d %d", &a, &b, &c); d[a][b] = min(c, d[a][b]); } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (d[i][j] > d[i][k] + d[k][j]) { d[i][j] = d[i][k] + d[k][j]; } } } } int result = max_val; for (int i = 1; i <= n; i++) { result = min(result, d[i][i]); } if (result == max_val) result = -1; printf("#%d %d\n", test_case, result); } return 0; }