일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- dfs
- 크루스칼
- Overfitting
- 너비 우선 탐색
- 세그먼트 트리
- 조합론
- 우선 순위 큐
- c++
- lazy propagation
- 분할 정복
- 다익스트라
- 플로이드 와샬
- 자바스크립트
- 회고록
- pytorch
- object detection
- back propagation
- 이분 탐색
- dropout
- 알고리즘
- 미래는_현재와_과거로
- 백트래킹
- BFS
- tensorflow
- 가끔은 말로
- 문자열
- DP
- NEXT
- 가끔은_말로
- 2023
Archives
- Today
- Total
Doby's Lab
[알고리즘] 백준 14938번: 서강그라운드 (C++) 본문
https://www.acmicpc.net/problem/14938
판단 실수로 플로이드 와샬 안에서도 최단 경로를 갱신할 때 m(수색 범위) 이내에 있는 것만 갱신해줬었다.
어쨌거나 최단 경로들은 모두 갱신한 후에 m(수색 범위) 안에서 갈 수 있는 길을 찾아야 하는 것이 포인트다.
#include <iostream>
#include <cmath>
#define MAX 100 + 1
#define INF 987654321
using namespace std;
int graph[MAX][MAX];
int item[MAX];
int n, m, r;
void floydWarshall() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (graph[i][k] + graph[k][j] < graph[i][j]) {
graph[i][j] = graph[i][k] + graph[k][j];
}
}
}
}
for (int i = 1; i <= n; i++) {
graph[i][i] = 0;
}
}
int main() {
cin >> n >> m >> r;
for (int i = 1; i <= n; i++) {
cin >> item[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
graph[i][j] = INF;
}
}
for (int i = 0; i < r; i++) {
int a, b, c;
cin >> a >> b >> c;
graph[a][b] = c;
graph[b][a] = c;
}
floydWarshall();
int maxValue = 0;
for (int i = 1; i <= n; i++) {
int sum = 0;
for (int j = 1; j <= n; j++) {
if (graph[i][j] <= m) {
sum += item[j];
}
}
maxValue = max(maxValue, sum);
}
cout << maxValue;
return 0;
}
728x90
'PS > BOJ' 카테고리의 다른 글
[알고리즘] 백준 2665번: 미로만들기 (C++) (0) | 2021.12.07 |
---|---|
[알고리즘] 백준 11780번: 플로이드 2 (C++), 최단 경로 발생 노드 담기 (0) | 2021.12.06 |
[알고리즘] 백준 2660번: 회장뽑기 (C++) (0) | 2021.12.06 |
[알고리즘] 백준 1613번: 역사 (C++) (0) | 2021.12.06 |
[알고리즘] 백준 10159번: 저울 (C++) (0) | 2021.12.06 |