Submission #6426460

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <functional>
#include <map>
#include <queue>
#define REP(i,n) for(int (i)=0; (i)<(n); (i)++)
using namespace std;
using ll = long long;
ll MOD = 1e9+7;

ll shortest;
ll s,g;

ll rec(ll cnt, ll line, vector<vector<ll>> mp, string str){
    if(cnt > mp[s][line]){
        //printf("s=%d, line=%d, mp[%d][%d]=%d, cnt=%d\n", s, line, s, line, mp[s][line], cnt);
//        cout << s << "," << line << "," << mp[s][line] << "," << cnt << endl;
        return 0;
    }else if(cnt == shortest){
        if(line==g){
            return 1;
        }else{
            return 0;
        }
    }
    ll ret = 0;;
    vector<vector<ll>> omp = mp;
    for(int i = 0; i < mp[0].size(); i++){
        if(mp[line][i] != 0 && mp[line][i] != 1e18){
            ll tmp = mp[line][i];
            //mp[line][i] = 0;
            mp[i][line] = 0;
            ret += rec(cnt+1, i, mp, str + to_string(i));
        }
        mp = omp;
    }
    return ret;
}

void warshall_floyd(vector<vector<ll>> &mp){
    ll n = mp[0].size();
    REP(k, n){
        REP(i, n){
            REP(j, n){
                mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
            }
        }
    }
    REP(i, n){
        REP(j, n){
            if(i == j){
                mp[i][j] = 0;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, m;
    cin >> n >> s >> g >> m;
    s--;
    g--;
    vector<vector<ll>> mp(n+1, vector<ll>(n+1, 1e18));
    vector<vector<ll>> omp(n+1, vector<ll>(n+1, 1e18));
    int x, y;
    REP(i, m){
        cin >> x >> y;
        x--;
        y--;
        mp[x][y]=1;
        mp[y][x]=1;
    }
    omp = mp;
//    REP(i, n){
//        REP(j, n){
//            if(mp[i][j] == 1e18){
//                cout << 0 << " ";
//            }else{
//                cout << mp[i][j] << " ";
//            }
//        }
//        cout << endl;
//    }

    
    warshall_floyd(mp);
    shortest = mp[s][g];
//    cout << shortest << endl;
    ll ans = 1e18;
//    REP(i, n){
//        REP(j, n){
//            cout << mp[i][j] << " ";
//        }
//        cout << endl;
//    }
    ans = rec(0, s, omp, "0");
    
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result