[白俊]1865号虫洞

1865号:虫洞
これは負の幹線の問題です.
bfsなので悩んでいて、どうしたらいいのか分からない.
最短距離の問題を解決してから長い間、ディエストラは思い出せなかったが、ディエストラではなかった.
初めてベルマンフォード問題に触れた.
実際、ベルマンフォードアルゴリズムはまだすべて理解できない.

は、Dist[adj node]の描画方法の1つである(現在のノードの中で最もコストが低いが、まだ確定していない最もコストが低いノードの中でノードを選択し、そのノードを通過する経路コストが最も低い隣接ノードのdist[adj node])を更新する.
対照的に、

ベルマンフォードは確かに非常に探索的であることは理解できる.

->したがってdextraのプロセスもここに含まれているので,無条件に解くことができる.

->確かに遅い(O(VE)

)

も陰の幹線によって1サイクル(目標は「最短経路」を求めるため)が発生し、場合によっては陰の幹線によって、このエッジを通って「繰り返す!」小さくすればするほど無限に繰り返される場合があるので),−INNFITY値も理解できる.

しかし動作方式自体はよく理解できないので,普遍的なベルマンフォードアルゴリズム問題の解決方法しか考えていない.

今はまだ理解できませんが、個人的には説明が良い文章だと思います.
ベルマンフォードアルゴリズム

まず、最も重要なのは、ベルマンフォードダン、ディックスタワーなどの特定のノードから各ノードへの最短経路を探す方法です.

したがって、distテーブルが存在する場合、この2つの方法は、「ノードごとの最低コスト」

を格納することができる.

distテーブルはINFINITY値に初期化され、

の始点だけを0にする共通点がある.

ベルマンフォードは、その後、ノードの個数がvであれば、v-1回で次のステップを繰り返します.

のすべてのedgeについて、次の操作を行います.

edgeは{from,to,cost}を有する.

dist[from]≠INFINITY&&dist[to]>dist[from]+cost->dist[to]=dist[from]+をcostに更新します.

dist[from]≠INFINITY、すなわちfromノードにアクセスしたことがある場合.

ベルマンフォードは「負の幹線」による周期の存在を確認できる.上記の繰り返し手順をもう一度実行します.

のすべてのedgeについて、次の操作を行います.

edgeは{from,to,cost}を有する.

dist[from]≠INFINITY&&dist[to]>dist[from]+cost->dist[to]=dist[from]+をcostに更新します.

dist[from]≠INFINITY、すなわちfromノードにアクセスしたことがある場合.

v回目に実行されたこの繰返しでは、distテーブルの更新が再び発生し、これは負のシーケンス幹線によるループを意味する.

誰かがこの問題をまとめた。

文章を読む-解答と論争を徹底的に取り除く。
しかしベルマンフォードも完全に理解していなかったので、この文章の中で、私が理解できる部分だけを選んで、再び解いた.
打たれてまた浮かび上がったが、完全に理解できなかった.

この問題。

の開始点は与えられなかった.

基本的に考えられるベルマンフォードアルゴリズムは,特定の起点から,負の幹線が存在する図形上,各ノードの最短距離を探すアルゴリズムである.

しかし,この問題は,「1」を起点として解くだけでは,1を起点とすると見つからない負のコヒーレンス周期が存在する可能性がある.

によれば,すべてのノードが起点となるように解くべきである.つまり、すべてのノードを同時に始点としてナビゲートできるようにすることができます.->dist tableのすべてのノードの値をINFではなく0に設定します.

によると、この部分は

ベルマンフォード、その後、ノードの個数がnである場合、n−1は次のステップを繰り返す.

のすべてのedgeについて、次の操作を行います.

edgeは{from,to,cost}を有する.

dist[from]≠INFINITY&&dist[to]>dist[from]+cost->dist[to]=dist[from]+をcostに更新します.

dist[from]≠INFINITY、すなわちfromノードにアクセスしたことがある場合.

ここで、dist[from]≠INFINITYを確認する必要はありません.

ですが、もしそうであれば、dist表の更新は負幹線を通過する場合にのみ適用されます.

したがって、すべてのエッジの緩和をn-1回繰り返す場合は、ループを必要とせずに、ある点からノードへの最短パスを設定する必要があります.

n回目に「すべてのエッジの緩和」が行われたときにupdateがあった場合、負の水平線によるループが「任意のノードから」最短経路で発生していることを意味する.

と理解される.

実施の面で

道路の双方向虫洞は一方向であるため、

特定from,toのedgeは最低コストを格納したいだけです.ノード数が500個しかないので、matrixを使用しました.

public class Main {
    public static final int TIME_INIT = 10001;
    public static int n,m,w; // the number of nodes, edges, holes
    public static int[][] matrix = new int[500][500];
    //public static List<int[]>[] graph = new ArrayList[500];
    public static List<int[]> edges = new ArrayList<>();
    public static int[] dist = new int[500];
    public static void Setting() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int test =0,v1=0,v2=0,c=0;
        test = Integer.parseInt(br.readLine());
        for(int t=0;t<test;t++){
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());
            // init dist table as the start node is 0
            Arrays.fill(dist, 0);
            // init matrix
            for(int i=0;i<n;i++)
                Arrays.fill(matrix[i],TIME_INIT);
            // get the  edge info
            for(int e=0;e<m;e++){
                st = new StringTokenizer(br.readLine());
                v1 = Integer.parseInt(st.nextToken())-1;
                v2 = Integer.parseInt(st.nextToken())-1;
                c = Integer.parseInt(st.nextToken());
                if(matrix[v1][v2]>c) matrix[v1][v2]=c;
                if(matrix[v2][v1]>c) matrix[v2][v1]=c;
            }
            // get the hole info
            for(int h=0;h<w;h++){
                st = new StringTokenizer(br.readLine());
                v1 = Integer.parseInt(st.nextToken())-1;
                v2 = Integer.parseInt(st.nextToken())-1;
                c = Integer.parseInt(st.nextToken())*(-1);
                if(matrix[v1][v2]>c) matrix[v1][v2]=c;

            }

            boolean res =solve();
            if(res) System.out.println("YES");
            else System.out.println("NO");
        }
    }
    public static void print(){
        System.out.println();
        for(int i=0;i<n;i++){
            System.out.print(dist[i]+",");
        }
    }
    // if return true --> it has cycle of negative edge
    public static boolean solve() {
        //  n 번 수행하는 것은, 음의간선 순회를 확인하기 위함.
        int cur=0,next=0,c=0;
        for(int i=0;i<n;i++){
            // 모든 간선에 대하여 수행 한다. 간선을
            for(int start=0;start<n;start++){
                for(int end=0;end<n;end++){
                    // 이거는 간선이 아님
                    if(matrix[start][end]==TIME_INIT)continue;

                    // 갱신이 일어나는 경우
                    if(dist[end]>(dist[start]+matrix[start][end])){
                        dist[end]=dist[start]+matrix[start][end];
                        //print();
                        if(i == n-1) return true;
                    }
                }
            }
        }
        return false;
    }
    public static void main(String[] args) throws IOException {
        Setting();

    }
}