1238번: 파티

https://www.acmicpc.net/problem/1238

#include<stdio.h>
#include<algorithm>
int map[1010][1010], d[1010][1010], cnt[1010], n, m, x, MAX, sum[1010], que[10010], tmp[1010], a, b, c, head, tail;
int main()
{
    int i, j;
    scanf("%d%d%d", &n, &m, &x);
    for (i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        map[a][++cnt[a]] = b;
        d[a][b] = c;
    }
    for (i = 1; i <= n; i++)
    {
        head = 0;
        tail = 1;
        que[1] = i;
        std::fill(sum + 1, sum + 1 + 1000, 2147483647);
        sum[i] = 0;
        while (head<tail)
        {
            head++;
            for (j = 1; j <= cnt[que[head]]; j++)
            {
                if (sum[map[que[head]][j]]>sum[que[head]] + d[que[head]][map[que[head]][j]])
                {
                    sum[map[que[head]][j]] = sum[que[head]] + d[que[head]][map[que[head]][j]];
                    que[++tail] = map[que[head]][j];
                }
            }
        }
        tmp[i] = sum[x];
    }
    head = 0;
    tail = 1;
    que[1] = x;
    std::fill(sum + 1, sum + 1 + 1000, 2147483647);
    sum[x] = 0;
    while (head<tail)
    {
        head++;
        for (j = 1; j <= cnt[que[head]]; j++)
        {
            if (sum[map[que[head]][j]]>sum[que[head]] + d[que[head]][map[que[head]][j]])
            {
                sum[map[que[head]][j]] = sum[que[head]] + d[que[head]][map[que[head]][j]];
                que[++tail] = map[que[head]][j];
            }
        }
    }
    for (i = 1; i <= n; i++)
    {
        if (tmp[i] + sum[i]>MAX)
        {
            MAX = tmp[i] + sum[i];
        }
    }
    printf("%d", MAX);
    return 0;
}