[JSOI 2010] 여행 문제풀이

제목 링크
도론+DP의 한 문제는 경로를 가장 짧게 하고 길이에 따라 작은 경로에서 큰 경로로 정렬한 후에 앞\(fr\)개의 경로를 걷는 경로에 배치할 것이며 매번 교환할 때마다 앞\(fr\)개의 경로와\(fr\)후의 경로를 교환할 것이다.\(fr\)가 얼마인지 우리는 매거\(fr\)하고 DP에서\(ans\)를 구할 수 있다.
설정\(f[i][j][k]\)는 1에서\(i\)까지 앞\(fr\)개의 경로에\(j\)줄이 지나갔음을 나타낸다.\(k\)개의 경로가 지나간 최소 길이를 교환한 다음에 세 가지 상황으로 나누어 옮기면 된다. 어떻게 옮기는지 코드를 보자. 사실 나는 쓰고 싶지 않다. 주로 코드가 구리고 길다.

                if(num<=fr)
                {
                    if(jjjdis[xxx][jjj][kkk]+e[jjj+1].w)
                    {
                        dis[son][jjj+1][kkk]=dis[xxx][jjj][kkk]+e[jjj+1].w;
                        if(!vis[son][jjj+1][kkk])
                            vis[son][jjj+1][kkk]=1,txt.xx=son,txt.jj=jjj+1,txt.kk=kkk,q.push(txt);
                    }
                }
                else
                {
                    if(jjjdis[xxx][jjj][kkk]+e[jjj+1].w)
                    {
                        dis[son][jjj+1][kkk+1]=dis[xxx][jjj][kkk]+e[jjj+1].w;
                        if(!vis[son][jjj+1][kkk+1])
                            vis[son][jjj+1][kkk+1]=1,txt.xx=son,txt.jj=jjj+1,txt.kk=kkk+1,q.push(txt);
                    }
                    if(dis[son][jjj][kkk]>dis[xxx][jjj][kkk]+e[num].w)
                    {
                        dis[son][jjj][kkk]=dis[xxx][jjj][kkk]+e[num].w;
                        if(!vis[son][jjj][kkk])
                            vis[son][jjj][kkk]=1,txt.xx=son,txt.jj=jjj,txt.kk=kkk,q.push(txt);
                    }
                }
            }
        }

우리가 편의를 위해 매번 경로를 교환할 때 반드시 어느 경로와 교환하는지 보지 않아도 된다. 어차피 앞\(fr\)개의 경로는 모두 찾을 수 있으니 어릴 때부터 크게 늘리면 된다.
모든 코드를 붙여주세요.

#include
using namespace std;
struct node
{
    int x,y,w;
} e[100003];
struct nod
{
    int xx,jj,kk;
} p,txt;
queueq;
int n,m,k,vis[53][153][23],dis[53][153][23],ans=1e9,xxx,jjj,kkk,num,son;
vectorl[100003];
int cmp(node nx,node ny)
{
    return nx.wdis[xxx][jjj][kkk]+e[jjj+1].w)
                    {
                        dis[son][jjj+1][kkk]=dis[xxx][jjj][kkk]+e[jjj+1].w;
                        if(!vis[son][jjj+1][kkk])
                            vis[son][jjj+1][kkk]=1,txt.xx=son,txt.jj=jjj+1,txt.kk=kkk,q.push(txt);
                    }
                }
                else
                {
                    if(jjjdis[xxx][jjj][kkk]+e[jjj+1].w)
                    {
                        dis[son][jjj+1][kkk+1]=dis[xxx][jjj][kkk]+e[jjj+1].w;
                        if(!vis[son][jjj+1][kkk+1])
                            vis[son][jjj+1][kkk+1]=1,txt.xx=son,txt.jj=jjj+1,txt.kk=kkk+1,q.push(txt);
                    }
                    if(dis[son][jjj][kkk]>dis[xxx][jjj][kkk]+e[num].w)
                    {
                        dis[son][jjj][kkk]=dis[xxx][jjj][kkk]+e[num].w;
                        if(!vis[son][jjj][kkk])
                            vis[son][jjj][kkk]=1,txt.xx=son,txt.jj=jjj,txt.kk=kkk,q.push(txt);
                    }
                }
            }
        }
        for(int i=0; i<=k; i++)
            ans=min(ans,dis[n][fr][i]);
    }
    cout<