14944 굿점원

case를 잘 구하면 되는 문제다.

"친구가 만들어 준 길을 다 걷지 않았다면 마저 걸어야 한다." 라는 말은 다른 모든 친구들의 길을 포함하는게 아니고

i번째 친구의 길을 이용하기로 마음 먹었으면 마지막 종착지가 새 집이더라도

새 집에서 기존 루트로 연결되는 길까지 걸리는 시간도 포함해야 한다는 것이다.

그렇기 때문에 새 집으로 연결하는 루트의 전체 길이만 줄 뿐 들어가는길, 나오는길 길이를 따로주지 않는다.

경로의 길이는 누적합을 활용한다.

경우 1.

0 - A - 새집 - B - N - A+1

A - A+1 < B - N

경우 2.

0 - A - 새집 - B - N - B - 새집 - A - B-1

B-1 - B < w + B - N  (w = A - 새집 - B)

경우 3.

0 - B - 새집 - A - N 

== 0 - A - 새집 - B - A - N

A - B < else

경우 4.

0 - A - 새집 - B - 새집 - A - N

== 0 - B - 새집 - A - 새집 - B - N

w < else

경우 5.

0 - A - 새집 - B - N

A - B가 바로 연결

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, m;
long long d[10001], res = 2e9;
 
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &d[i]), d[i] += d[i - 1];
    for (int i = 0, u, v, w; i < m; i++) {
        scanf("%d %d %d", &u, &v, &w);
        if (u > v) swap(u, v);
        if (v - u == 1) res = min(res, d[u] + w + d[n] - d[v]);
        res = min(res, d[u] + w + (d[n] - d[v]) + d[n] - d[u + 1]);
        res = min(res, w * 2 + (d[n] - d[v]) * 2 + d[v - 1]);
        res = min(res, d[v] + w + d[n] - d[u]);
        res = min(res, w * 2 + d[n]);
    }
    printf("%lld", res);
    return 0;
}