noyのブログ

プログラミングとかゲームとか

ABC021 C 正直者の高橋君

C: 正直者の高橋くん - AtCoder Beginner Contest 021 | AtCoder

状態

AC
AC
AC
WA
AC
.
.
.
AC

_人人人人人人人人人人_
> なぜかACできない <
 ̄Y^Y^Y^Y^Y^Y^Y^Y^Y ̄

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define itrep(it, a) for(it = (a).begin(); it != (a).end(); it++)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
#define INF (1 << 29)
using namespace std;
 
const int kn = 105;
int atlas[kn][kn];
 
int warshallFloyd(int n, int start, int goal){
    rep(k,n){
        rep(i,n){
            rep(j,n){
                atlas[i][j] = min(atlas[i][j], atlas[i][k] + atlas[k][j]);
            }
        }
    }
    return atlas[start][goal];
}
 
long long numberOfDirections(int n, int shortestPath, int start, int goal){
    long long path, retval = 1;
    range(i,1,shortestPath){
        path = 0;
        rep(j,n){
            if(atlas[start][j] == i && atlas[j][goal] == shortestPath - i) path++;
        }
        retval = (retval * path) % 100000007;
    }
    return retval;
} 
 
int main(){
    int n, m, a, b;
    cin >> n >> a >> b >> m;
    //0からに合わせる
    a--; b--;
    rep(i,kn) rep(j,kn) atlas[i][j] = INF;
    rep(i,m){
        int x, y;
        cin >> x >> y;
        x--; y--;
        atlas[x][y] = atlas[y][x] = 1;
    }
    cout << numberOfDirections(n, warshallFloyd(n, a, b), a, b) << endl;
}

トポロジカルソートやメモ化再帰でもないなにか。

出発地点aから目的地bまでの距離を求める。
その後、aからbまでの通る道を数えて積を求めている。

点Aから点Bまでは2通りの道。点Bから点Cまでは5通りの道。
点Aから点Cまでの行き方は、2 * 5の10通り。
こんな計算を意識して書いた。

結果はコーナーケースに阻まれWA。
INFやretvalの計算を見直すも変わらず。

なぜだかわからないまま今日は断念。

今になって思えば、ワ―シャルフロイドじゃなくてダイクストラでも何の問題もなかった。