Solved.ac/Class 46 [BOJ] 백준 1865번: 웜홀 SPFA + SLF 로 풀었지만 일반적인 벨만포드 알고리즘이 더 빠름 웜홀 시작점을 저장하여 탐색하며 update 횟수를 cycle 배열에 저장하여 노드 수 이상 업데이트 되면 음의 사이클 [!] 노드 수가 N개일때 N개를 전부 탐색하는 path는 n-1 개이다 n번 탐색이 된 경우는 n-1번 움직였을때보다 최소의 경로 비용을 뜻하므로 음의 간선이 있음 #include #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long ll; void solve() { int n, m, w; vector v[501]; vector list; cin >> n >> m >> w;.. 2020. 6. 19. [BOJ] 백준 14938번: 서강그라운드 모든 지점에서 다익스트라를 반복하여 최대값을 찾는 문제 #include #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long ll; vector v[101]; int dist[101]; int item[101]; int n, m, r; bool visit[101] = { 0, }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> m >> r; for (int i = 1; i > item[i]; } for (int i = 0; i < r; i++) { .. 2020. 6. 19. [BOJ] 백준 11779번: 최소비용 구하기 2 #include #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long ll; vector v[1001]; int dist[1001]; int pre[1001]; int n, m; int s, e; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> m; memset(pre, -1, sizeof(pre)); for (int i = 1; i > a >> b >> c; v[a].push_back({ b,c }); } cin >> s >> e; priority_.. 2020. 6. 19. [BOJ] 백준 1238번: 파티 주어진 입력을 정방향, 역방향 2개의 벡터로 저장하여 파티가 열리는 노드를 시작으로 다익스트라를 2번 수행하여 오고 가는데 걸린 최단 경로 합의 최대를 출력하는 문제 #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long ll; vector v[10001]; vector v2[10001]; int dist[10001]; int dist2[10001]; int n, m, x; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> m >> x; for (int .. 2020. 6. 19. 이전 1 2 다음
