ABC 21 C - 正直者の高橋くん ( Dijkstra + DP )

C: 正直者の高橋くん - AtCoder Beginner Contest 021 | AtCoder
経路数の計算、dijkstra を一回やって disをたどりながら dpするだけだね。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 2;
const int MAXM = 200 + 2;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

int add(int &x, int v){
    x += v;
    x %= MOD, x += MOD, x %= MOD;
    return x;
}

int n;
int a, b;
int m;
vector<int> G[ MAXN ];

struct Dijkstra{
    int dis[ MAXN ], vis[ MAXN ];
    void solve(){
        memset( dis, INF, sizeof(dis) );
        priority_queue<pii, vector<pii>, greater<pii> > pq;
        pq.push( pii( dis[ a ] = 0, a ) );
        memset( vis, 0, sizeof(vis) );
        while( !pq.empty() ){
            int u = pq.top().second; pq.pop();
            if( vis[ u ] ) continue;
            vis[ u ] = 1;
            for(int v: G[ u ]){
                if( dis[ v ] > dis[ u ] + 1 ){
                    dis[ v ] = dis[ u ] + 1;
                    if( !vis[ v ] )
                        pq.push( pii( dis[ v ], v ) );
                }
            }
        }
    }
} dijkstra;

int memo[ MAXN ];

int dp(int u){
    if( u == a ) return 1;
    if( memo[ u ] >= 0 ) return memo[ u ];
    int res = 0;
    for(int v: G[ u ])
        if( dijkstra.dis[ v ] == dijkstra.dis[ u ] - 1 )
            add( res, dp( v ) );
    return memo[ u ] = res;
}

void solve(){
    dijkstra.solve();
    memset( memo, -1, sizeof(memo) );
    printf("%d\n", dp( b ));
}

int main(){
    scanf("%d", &n);
    scanf("%d%d", &a, &b);
    scanf("%d", &m);
    for(int i = 0; i < m; ++i){
        int x, y; scanf("%d%d", &x, &y);
        G[ x ].push_back( y );
        G[ y ].push_back( x );
    }
    solve();
    return 0;
}