質問する

質問リンク
これは、最短パスが見つかったグラフィックのうち、どのグラフィックから始まるかという問題です.
一般的なFloyWarshare問題では,ノード間の距離が与えられる.
通常、各ノード間の最短距離を求める必要があります.
この問題は正反対だ.
長い間悩んだ.
ノード間の1−2−3のように,2回通過する場合は容易に見つかるようである.
もし1-2-3-4が1-4の最短距離ならば、どのように求めるのはとても困惑しました.
しかし考えてみれば、1-2-3-4が最も短いという意味は1-2-4、1-3-4も最も短いという意味です.△つながっているから.
これで問題は解決できる.

例の正解は55で、下図のようになっています.

グラフから元の状態を推定することもできる.
それでは最短経路でない場合をチェックして、後で最短経路を加えれば解決です.
不可能な状況を-1に戻させてください.問題は少し友好的ではありませんか.
何が起こっているのか容易に思い出せない.
だからすべてのノードが接続できないのではないかと思ってunion-findを使ってみましたが、問題はすべてのノードが接続されていることです.
できないので質問をしましたが、
不可能な場合、このグラフは最初から最短距離ではありません.
逆に考えてみるのも容易ではありませんが、不可能な状況を説明していないので、とても慌てています.

code

/**
 * 백준 1507
 * 플로이드 워셜
*/
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

int n;
int graph[20][20];
bool check[20][20]={false};

int prim(void){
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i==j || i==k || k==j || i>j) continue;
                if(graph[i][j]==(graph[i][k]+graph[k][j])){
                    check[i][j]=true;
                }
                else if(graph[i][j]>(graph[i][k]+graph[k][j])){
                    return -1;
                }
            }
        }
    }

    int ret=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i<j && !check[i][j]){
                //cout<<"check : "<<i<<","<<j<<endl;
                ret+=graph[i][j];
            }
        }
    }
    return ret;
}

int main(void){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&graph[i][j]);
        }
    }
    
    int ans = prim();
    cout<<ans<<endl;
}