๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
Algorithm ๐Ÿง‘๐Ÿป‍๐Ÿ’ป/๋ฐฑ์ค€(BOJ)

[๋ฐฑ์ค€,c++] 14938๋ฒˆ - ์„œ๊ฐ•๊ทธ๋ผ์šด๋“œ

by dkswnkk 2021. 11. 14.

๋ฌธ์ œ

 

14938๋ฒˆ: ์„œ๊ฐ•๊ทธ๋ผ์šด๋“œ

์˜ˆ์€์ด๋Š” ์š”์ฆ˜ ๊ฐ€์žฅ ์ธ๊ธฐ๊ฐ€ ์žˆ๋Š” ๊ฒŒ์ž„ ์„œ๊ฐ•๊ทธ๋ผ์šด๋“œ๋ฅผ ์ฆ๊ธฐ๊ณ  ์žˆ๋‹ค. ์„œ๊ฐ•๊ทธ๋ผ์šด๋“œ๋Š” ์—ฌ๋Ÿฌ ์ง€์—ญ์ค‘ ํ•˜๋‚˜์˜ ์ง€์—ญ์— ๋‚™ํ•˜์‚ฐ์„ ํƒ€๊ณ  ๋‚™ํ•˜ํ•˜์—ฌ, ๊ทธ ์ง€์—ญ์— ๋–จ์–ด์ ธ ์žˆ๋Š” ์•„์ดํ…œ๋“ค์„ ์ด์šฉํ•ด ์„œ๋ฐ”์ด๋ฒŒ์„

www.acmicpc.net

 

์ฝ”๋“œ

#include <iostream>
#include <algorithm>
#define INF 1e9
using namespace std;

int n,m,r,ans;  //n=์ง€์—ญ์˜ ๊ฐฏ์ˆ˜, m=์ˆ˜์ƒ‰๋ฒ”์œ„, r=๊ธธ์ด์˜ ๊ฐฏ์ˆ˜
int graph[101][101];
int item[101];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>m>>r;

    for(int i=0; i<101; i++){
        fill(graph[i],graph[i]+101,INF);
    }
    for(int i=1; i<=n; i++){
        for(int k=1; k<=n; k++){
            if(i==k) graph[i][k]=1;
        }
    }

    for(int i=1; i<=n; i++){
        cin>>item[i];
    }

    for(int i=1; i<=r; i++){
        int a,b,c; cin>>a>>b>>c;
        graph[a][b]=c;
        graph[b][a]=c;
    }

    for(int i=1; i<=n; i++){
        for(int a=1; a<=n; a++){
            for(int b=1; b<=n; b++){
                graph[a][b]=min(graph[a][b],graph[a][i]+graph[i][b]);
            }
        }
    }
    for(int a=1; a<=n; a++){
        int temp=0;
        for(int b=1; b<=n; b++){
            if(graph[a][b]!=INF&&graph[a][b]<=m) temp+=item[b];
        }
        ans=max(ans,temp);
    }
    cout<<ans;
}

๋Œ“๊ธ€