AOJ2608 Minus One

問題概要
無向グラフについて2点, の最短経路をとしたとき、 （ただし, ）を満たす辺を追加したときの, 間の最短経路がとなるような辺はいくつ存在するか。
各辺の重みは1とする。

考えたこと
いまを考えた時, を満たせばよい。
すなわち, を考えればよく, これは頂点, について各点の最短経路を求め, からの距離を固定して条件を満たす辺を全探索すればよい。
計算量は

ACコード

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
 
typedef long long ll;
vector<vector<int>> g(100010);
int ds[100010];
int dg[100010];
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    
    
    int N, M, s, t; cin >> N >> M >> s >> t;

    s--; t--;

    REP(i,M){
        int x, y; cin >> x >> y;
        x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    REP(i,N) ds[i] = dg[i] = INT_MAX;

    {
        queue<int> q;
        q.push(s);
        ds[s] = 0;
        while(q.size()){
            int v = q.front();
            q.pop();

            for(int i=0; i<g[v].size(); i++){
                if(ds[g[v][i]] == INT_MAX){
                    ds[g[v][i]] = ds[v] + 1;
                    q.push(g[v][i]);
                }
            }
        }
    }

    
    {
        queue<int> q;
        q.push(t);
        dg[t] = 0;
        while(q.size()){
            int v = q.front();
            q.pop();

            for(int i=0; i<g[v].size(); i++){
                if(dg[g[v][i]] == INT_MAX){
                    dg[g[v][i]] = dg[v] + 1;
                    q.push(g[v][i]);
                }
            }
        }
    }

    map<ll, ll> mp, mp2;
    REP(i,N){
        mp[ds[i]]++;
        mp2[dg[i]]++;
    }

    int e = ds[t]-2;
    ll ans = 0;
    for(int i=0; i<=e; i++){
        int v = e-i;
        
        ans += mp[i] * mp2[v];
    }
    cout << ans << endl;
    return 0;
}

使ったサイト
入力した数式をtex形式に変換してくれる
webdemo.myscript.com