๋ฌธ์
์ฝ๋
#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;
}
'Algorithm ๐ง๐ปโ๐ป > ๋ฐฑ์ค(BOJ)' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค,c++] 15240๋ฒ - Paint bucket (0) | 2021.11.17 |
---|---|
[๋ฐฑ์ค,c++] 1504๋ฒ - ํน์ ํ ์ต๋จ ๊ฒฝ๋ก (0) | 2021.11.17 |
[๋ฐฑ์ค,c++] 14950๋ฒ - ์ ๋ณต์ (0) | 2021.11.14 |
[๋ฐฑ์ค,c++] 1439๋ฒ - ๋ค์ง๊ธฐ (0) | 2021.11.14 |
[๋ฐฑ์ค,c++] 14923๋ฒ - ๋ฏธ๋ก ํ์ถ (0) | 2021.11.14 |
[๋ฐฑ์ค,c++] 14921๋ฒ - ์ฉ์ก ํฉ์ฑํ๊ธฐ (0) | 2021.11.14 |
๋๊ธ