- 백준 149382024년 10월 15일
- SiJun-Park
- 작성자
- 2024.10.15.:13
https://www.acmicpc.net/problem/14938
아이템 수가 각 좌표마다 있으며 자신이 갈 수 있는 범위가 정해집니다.
그러면 그 범위보다 적은 시간이 걸리는 경로로 이동을 하여야하고, 그 경로에 있는 모든 아이템을 다 더해주면 됩니다.
저는 플로이드 와샬 알고리즘을 사용하여서 가장 먼저 모든 좌표에 대한 거리를 계산을 하였습니다.
그리고 그 계산을 토대로 나의 범위 내에 있으면 아이템 총 개수를 더해주었습니다.
#include <iostream> #include <algorithm> #include <cstring> #include <string> #include <cmath> #include <queue> #include <list> #include <vector> #include <stack> #define ll long long #define INF 1000000000 using namespace std; int N, M, R; int item[101]; int map[101][101]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> M >> R; for (int i = 1; i <= N; i++) cin >> item[i]; // item amount for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if(i!=j) map[i][j] = INF; } } for (int i = 0; i < R; i++) { int A, B, C; cin >> A >> B >> C; map[A][B] = C; map[B][A] = C; } for (int k = 1; k <= N; k++) { for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { map[i][j] = min(map[i][j], map[i][k] + map[k][j]); } } } int result = 0; for (int i = 1; i <= N; i++) { int ans = 0; for (int j = 1; j <= N; j++) { if (map[i][j] <= M) ans += item[j]; } result = max(result, ans); } cout << result; }
다음글이전글이전 글이 없습니다.댓글
스킨 업데이트 안내
현재 이용하고 계신 스킨의 버전보다 더 높은 최신 버전이 감지 되었습니다. 최신버전 스킨 파일을 다운로드 받을 수 있는 페이지로 이동하시겠습니까?
("아니오" 를 선택할 시 30일 동안 최신 버전이 감지되어도 모달 창이 표시되지 않습니다.)