문제

굳이 왜 써놨지 하는 문장은 한번 더 깊게 읽어봐야 한다는 교훈을 준 문제이다.

문제 링크

문제 접근

  • 딱봐도 길찾기 문제 구나 하고 바로 다익스트라로 접근하려 했다.
  • 근데 최단경로가 아니라 이건 최장경로 문제라는 걸 예제가 안돌아가는 걸 보고 알았다.
  • 최장 경로는 어떻게 찾아야 할까…

최장 경로 찾기

  • 최장 경로를 어떻게 찾을까 하다가 지문에 힌트가 있는 것을 발견했다.
  • “경주로는 1번 지점을 제외한 어느 지점에서 출발하여도 1번 지점을 지나가지 않고서는 같은 지점으로 돌아올 수 없도록 되어 있다.”
  • 즉 이 문제는 1번을 거치지 않고는 Cycle이 존재하지 않는 DAG로 볼 수 있다.
  • 이걸 알고 난 후에 위상정렬이 가능하겠다는 생각이 들었다.
  • 하나씩 edge를 지우면서 각 노드까지의 최대 값을 업데이트하고 incoming edge가 0인 애들을 방문한다.
  • 최대값을 업데이트할 때는 경로를 기록하는 pre 어레이도 업데이트 해준다.
  • 이를 통해 d[1]에 남는 값이 최대값이 된다.

코드

#include <cstdio>
#include <vector>
#define pii pair<int, int>
using namespace std;
int cnt, n, m, p, q, r, d[1001], pre[1001], in[1001], trace[1001];
vector<pii> v[1001];
int main(){
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++){
        scanf("%d %d %d", &p, &q, &r);
        if(p == 1)d[q] = r, pre[q] = 1;
        else{
            v[p].push_back(pii(r, q));
            in[q]++;
        }
    }
    for(int i = 1; i <= n; i++){
        if(in[i])continue;
        for(int j = 0; j < v[i].size(); j++){
            int nv = v[i][j].first, nx = v[i][j].second;
            if(d[nx] < d[i] + nv){
                d[nx] = d[i] + nv;
                pre[nx] = i;
            }
            in[nx]--;
        }
        in[i] = 1, i = -1;
    }
    trace[cnt++] = 1;
    while(pre[1] != 1){
        trace[cnt++] = pre[1];
        pre[1] = pre[pre[1]];
    }
    

    printf("%d\n1 ", d[1]); 
    for(int i = cnt - 1; i >= 0; i--)printf("%d ", trace[i]);
}

느낀점

  • 문제 속에 답이 있다….!!!!!!