全頂点対最短経路問題（ABC051D - Candidates of No Shortest Paths）

コンテストの時だけ思い出したように進捗を生むのも良くないと思うので、精進をしようと思います。なお、証明とかがガバガバかもしれませんのでご了承ください。

現在の私にとっては、苦手だったり勘違いしなければコンテスト時間内に、そうでなくても時間をかければだいたい解けるのが400点くらいです。ということで、400点問題から埋めていこうと思います。（それ以前から埋めると途中で面倒になってやめそうなので）
400点問題は現在100問くらいありますね
AtCoder Scores

今回はこれ（ABC051D - Candidates of No Shortest Paths）
atcoder.jp
最初問題文を良く読んでいなかったので、「どの異なる2頂点間の、どの最短経路」という条件を読み違え、最小全域木問題だと思ってクラスカル法（ついでにプリム法）を実装したり、単一始点最短経路問題だと思って経路記憶ダイクストラを実装したりしていました（これで一時間半溶かした）。まあ実装の練習＋ライブラリ作成ということで…

「どの異なる2頂点間の、どの最短経路」、つまり全頂点対最短経路問題なのでWarshall–Floydを使います。（計算量はV^3ですがV=100と小さいので大丈夫（ここで読み違いに気づくべき）)
この時、あるEdgeがどの最短経路にも使われていないことと、(辺の長さ)>(辺の両端の二頂点間の最短距離)となることは同値なので、c>d(a,b)となる辺の本数を出力して終わりだと思います。
まず「ある異なる2頂点(a,b)間の、全ての最短経路(コストd(a,b))」について、他の任意の二頂点c,fを考えると、もしedge(c,f)がその最短経路に属していればd(a,c)+edge(c,f)+d(f,b)==d(a,b)となるはずです。逆も自明でしょう。そして、d(a,c)+d(c,f)+d(f,b)=d(a,b)のはずなので、d(a,c)+edge(c,f)+d(f,b)==d(a,b)はd(c,f)==e(c,f)と同値です。ここからわかります。
コード：計算量O(V^3+E)=O(V^3)

#include <stdio.h>
#include <stdlib.h>
#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;
    Warshall_Floyd(int N): V(N){
        d = new long long int[V*V];
        edges=new vector<  pair<int,int>  >[V];
        rep(i,V*V){
            d[i]=LLINF;
        }
    }
    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;
    }
    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
         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 V,E;
    scanf("%d %d",&V,&E);
    Warshall_Floyd WF(V);
    rep(i,E){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        a--;b--;
        WF.push_edges(a,b,c);
    }
    int ans=0;
    WF.solve();
    rep(i,V){
        rep(j,WF.edges[i].size()){
            if( (long long int)(WF.edges[i][j].first) > WF.ite(i,WF.edges[i][j].second ))ans++;
        }
    }
    WF.free_wf();
    printf("%d\n",ans/2);
}

あと別にdijkstraを各頂点で回すのでも、だいたい同じ要領でできますね（めんどくさいけど）（priority_queue使えば計算量O(V*(V+E)log(V)）というわけであとで実装して確認します。