Submission #6426567


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, vector<vector<ll>> &vmp, string str){
    if(cnt > vmp[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;
            for(int j = 0; j < mp[0].size(); j++){
                mp[j][line] = 0;
            }
            ret += rec(cnt+1, i, mp, vmp, 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){
            if(omp[i][j] == 1e18){
                omp[i][j] = 0;
            }
            cout << omp[i][j] << " ";
        }
        cout << endl;
    }
    ans = rec(0, s, omp, mp, "0");
    
    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task C - 正直者の高橋くん
User tomiik
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2620 Byte
Status WA
Exec Time 2104 ms
Memory 17024 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
WA × 2
WA × 26
TLE × 6
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt WA 1 ms 256 KB
subtask0_sample_02.txt WA 1 ms 256 KB
subtask1_01.txt WA 56 ms 17024 KB
subtask1_02.txt WA 56 ms 17024 KB
subtask1_03.txt WA 1 ms 256 KB
subtask1_04.txt TLE 2104 ms 11544 KB
subtask1_05.txt TLE 2104 ms 8892 KB
subtask1_06.txt WA 2 ms 384 KB
subtask1_07.txt WA 2 ms 384 KB
subtask1_08.txt WA 52 ms 868 KB
subtask1_09.txt WA 14 ms 752 KB
subtask1_10.txt WA 3 ms 512 KB
subtask1_11.txt WA 528 ms 3248 KB
subtask1_12.txt TLE 2104 ms 8552 KB
subtask1_13.txt TLE 2103 ms 4076 KB
subtask1_14.txt TLE 2104 ms 8556 KB
subtask1_15.txt TLE 2103 ms 4408 KB
subtask1_16.txt WA 22 ms 1580 KB
subtask1_17.txt WA 27 ms 1416 KB
subtask1_18.txt WA 24 ms 1412 KB
subtask1_19.txt WA 6 ms 912 KB
subtask1_20.txt WA 14 ms 1056 KB
subtask1_21.txt WA 19 ms 1256 KB
subtask1_22.txt WA 8 ms 1032 KB
subtask1_23.txt WA 49 ms 1904 KB
subtask1_24.txt WA 53 ms 2548 KB
subtask1_25.txt WA 21 ms 2380 KB
subtask1_26.txt WA 23 ms 2060 KB
subtask1_27.txt WA 39 ms 2688 KB
subtask1_28.txt WA 54 ms 920 KB
subtask1_29.txt WA 5 ms 384 KB
subtask1_30.txt WA 1 ms 256 KB