dpを用いて最短経路の算出

Question

問題

問題

###質問内容
上記のAtCoderの問題をx_j→K→y_jの二つに分けてdpで求めようと思ったのですが、無向グラフのように道筋が多数ある場合の漸化式の立て方が分からないので教えてください。また、dpで無理な場合や他のより効率的なやり方がある場合は考え方を教えてくださると助かります。よろしくお願いいたします。

###書きかけのコード

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int[] a=new int[n-1]; //頂点a
        int[] b=new int[n-1]; //頂点b
        int[] c=new int[n-1]; //距離c
        for(int i=0;i<n-1;i++){
            a[i]=scan.nextInt();
            b[i]=scan.bextint();
            c[i]=scan.nextInt();
        }
        int Q=scan.nextInt();
        int K=scan.nextInt();
        int[] x=new int[Q]; //始点x
        int[] y=new int[Q]; //終点y
        int[][] dp1=new int[Q][K+1]; //xからのdp
        int[][] dp2=new int[Q][N+1]; //Kからのdp

        for(int i=0;i<Q;i++){
            x[i]=scan.nextInt();
            y[i]=scan.nextInt();
            
        }

    }
}

Answer 1

究極的にはatcoderの解説を読んでもらうのが一番なのですが...

この問題は多分木問題です。DPで解決する問題ではありません。
rootがKになる木構造を書くとよくわかると思います。
オーソドックスに親と子のノード情報を持つクラスを実装して繋げていくだけで解答はできます、がLTEを回避するにはいろいろと工夫が必要になると思われます。
（その手法が解説には書いてあります）

あんまり詳しく書いていないですが、努力して実装してみてほしいです。

Comments

[grape_ll]

dpではないのですね。
解説を読んで実装できるよう頑張りますが詰まってしまったら質問させていただきたいです．よろしくお願いします．

[hope_mucci]

木構造を理解していないと解説の理解も難しいかもしれませんが、頑張ってください。
やや専門的にはなりますが、アルゴリズムとデータ構造を簡単に解説しているサイトを張っておきます。
https://programming-place.net/ppp/contents/algorithm/index.html

Answer 2

ダイクストラ法でいいのでは？

Comments

[grape_ll]

このような方法があるのですね．
大変参考になりました．