14938) ㅅㄱ그라운드

#include <stdio.h>
#include <stdlib.h>

#define INF 1000;

int choose(int *path, int n, int *found)
{
int i, min, minpos;
min = INF;
minpos = -1;

for (i = 0; i < n; i++)
{
if (path[i] < min && found[i] == 0)
{
min = path[i];
minpos = i;
}
}

return minpos;
}

int collect(int from, int distance, int ** arr, int * item, int now,
int * path, int number, int * found)

{
int quba = 0;
int i, u, w;

for (i = 0; i < number; i++)
{
path[i] = arr[from][i];
found[i] = 0;
}

found[from] = 1;
path[from] = 0;
quba += item[from];

for (i = 0; i < number - 1; i++)
{

u = choose(path, number, found);
if (u == -1)
{
continue;
}

found[u] = 1;

for (w = 0; w < number; w++)
{
if (found[w] == 0)
{
if (path[u] + arr[u][w] < path[w])
{
path[w] = path[u] + arr[u][w];
}
}
}

if (path[u] <= distance)
quba += item[u];
}
return quba;
}

int main()
{
int number, distance, road;
scanf_s("%d %d %d", &number, &distance, &road);

int **arr;
arr = (int**)malloc(sizeof(int*) * number);
for (int i = 0; i < number; i++) 
arr[i] = (int*)malloc(sizeof(int) * number);

for (int i = 0; i < number; i++)
{
for (int j = 0; j < number; j++)
{
arr[i][j] = INF;
}
}

int imsi;
int * item;
item = (int*)malloc(sizeof(int*) * number);
for (int i = 0; i < number; i++)
{
scanf_s("%d", &imsi);
item[i] = imsi;
}

int * path;
path = (int*)malloc(sizeof(int*) * number);
for (int i = 0; i < number; i++)
path[i] = INF;

int * found;
found = (int*)malloc(sizeof(int*) * number);
for (int i = 0; i < number; i++)
found[i] = 0;

int from, to, value=0;
for (int i = 0; i < road; i++)
{
scanf_s("%d %d %d", &from, &to, &value);
from--; to--;
arr[from][to] = value;
arr[to][from] = value;
}

int get = 0; 
int temp = 0;
for (int i = 0; i < number; i++)
{
int now = 0;
temp= collect(i, distance, arr, item, now, path, number, found);
get = (get > temp) ? get : temp;
}

printf("%d", get);
free(arr);

return 0;
}

///////////////////////////

기존에 구현해둔 다익스트라를 활용했다.

간단하게 다익스트라 구현한 다음, 각 distance를 구하는 과정에서 수색 범위보다 적거나 같은 곳이 들어올 시

quba(가자)에 item을 더한 다음 누적시켜가며

get에서 그 최댓값을 갱신시켜가도록 했다

 

분명 맞는데 틀리다고 하길래 대체 왜지 했는데 <=를 해야 하는걸 <로 해서 몇십분을 헤맸다.

 

우에다레이나 사랑해~ 네 영상을 들으면서 풀었어