• 티스토리 홈
  • 프로필사진
    SiJun-Park
  • 방명록
  • 공지사항
  • 태그
  • 블로그 관리
  • 글 작성
SiJun-Park
  • 프로필사진
    SiJun-Park
    • 분류 전체보기 (121)
      • Unity (80)
        • RPG Project (39)
        • FPS Project (30)
        • 기타 - 개발 (11)
      • 개발 (35)
        • 임베디드 소프트웨어 (7)
        • 컴파일러 (6)
        • 기계학습 (8)
        • 보안 (8)
        • 그래픽스 (2)
        • 그 외 (4)
      • 코딩문제 (5)
  • 방문자 수
    • 전체:
    • 오늘:
    • 어제:
  • 최근 댓글
      등록된 댓글이 없습니다.
    • 최근 공지
        등록된 공지가 없습니다.
      # Home
      # 공지사항
      #
      # 태그
      # 검색결과
      # 방명록
      • 백준 14938
        2024년 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;
        }

        '코딩문제' 카테고리의 다른 글

        백준 17412  (0) 2024.10.22
        백준 14496  (0) 2024.10.19
        백준 6593  (0) 2024.10.10
        백준 14217  (0) 2024.10.10
        다음글
        다음 글이 없습니다.
        이전글
        이전 글이 없습니다.
        댓글
      조회된 결과가 없습니다.
      스킨 업데이트 안내
      현재 이용하고 계신 스킨의 버전보다 더 높은 최신 버전이 감지 되었습니다. 최신버전 스킨 파일을 다운로드 받을 수 있는 페이지로 이동하시겠습니까?
      ("아니오" 를 선택할 시 30일 동안 최신 버전이 감지되어도 모달 창이 표시되지 않습니다.)
      목차
      표시할 목차가 없습니다.
        • 안녕하세요
        • 감사해요
        • 잘있어요

        티스토리툴바