考察ワーシャルフロイド(ARC083D - Restoring Road Network)

atcoder.jp

まず、全ての頂点の間に の辺を張ります。その状態で全頂点間最短経路をワーシャルフロイドで求め、その最短距離が実際の最短距離より小さい時、そのような最短経路は存在しません。

なぜなら、
①まず、Aのu行目について見ていって、その行の中で最もが小さいvについて、町uとvは道で繋がれています。なぜなら、uから出発してvに行く時、他の頂点にまず向かうとその時点で最短距離を超えてしまうことがわかるからです。
➁①で存在することがわかった辺が存在するとして、またu行目について見ていって、次にが小さいu,vについて、
(a)すでに結ばれていて最短経路が入力より小さい：自明にそのような場合は不可能です。
(b)すでに結ばれていて最短経路が入力と同じ：そのu,vを結ぶ辺は必要ありませんが、
(c)まだ結ばれていない：明らかにそのu,vを結ぶ辺は必要です。なぜなら、以降追加される辺の長さはよりも長いため、それによってが実現されることはないからです。
③➁を繰り返して行くことで、可能な場合は全ての辺同士の間について(b)か(c)が成り立ちます。

道路の合計長さが最小となる時のその長さは、まず最初に全てのの長さの道を足しておき、最短距離をで初期化した後(b)が存在すればその道は消去する（合計長さから引く）ことで測定できます。

なかなかすぐ思いついた。調子良さそう。
あと、多分人生で初めて7日連続ACしました。コツは「精進しなきゃ…」と思わないことです。

#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>

 
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back
#define LLIandI pair<long long int , int>
#define ll long long

struct Warshall_Floyd{
    int V;
    long long int *d;//d[i_v1*V+i_v2]= v1tov2
    vector<  pair<int,int>  > *edges;
    long long total;
    bool *ifdelete;
    Warshall_Floyd(int N): V(N){
        d = new long long int[V*V];
        total=0;
        ifdelete=new bool[V*V];
        edges=new vector<  pair<int,int>  >[V];
        rep(i,V*V){
            d[i]=LLINF;
            ifdelete[i]=false;
        }
    }
    void push_edges(int a,int b, int c){
        edges[a].pb( mp(c,b));
        edges[b].pb( mp(c,a));
        if(ite(a,b)>c)d[a*V+b]=c;
        if(ite(b,a)>c)d[b*V+a]=c;
        total+=c;
    }
    long long int ite(int i,int j){
        return d[i*V+j];
    }
    void solve() { 
        for (int i = 0; i < V; i++)      // via
        for (int j = 0; j < V; j++)    // start
        for (int k = 0; k < V; k++)
        {// end
            if(i==j||j==k)continue;
            if(ifdelete[j*V+k]==false&&d[j*V+k]== ite(j,i) + ite(i,k) ){
                ifdelete[j*V+k]=true;ifdelete[k*V+j]=true;total-=d[j*V+k];
            }
            d[j*V+k] = min(ite(j,k), ite(j,i) + ite(i,k));
        }  
    }
    void free_wf(){
        delete[] d;
        delete[] edges;
    }
    
};

int main(void){
    int N;
    scanf("%d",&N);
    long long int A[300][300];
    Warshall_Floyd WF(N);
    rep(i,N){
        rep(j,N){
            scanf("%lld",&A[i][j]);
            if(i<j){WF.push_edges(i,j,A[i][j]);}
        }
    }
    WF.solve();
    rep(i,N){
        rep(j,N){
            if(WF.ite(i,j)<A[i][j]){printf("-1\n");return 0;}
        }
    }
    printf("%lld\n",WF.total);
}