Submission #3420638


Source Code Expand

#include<iostream>
#include<queue>
#define MAX_N 101
#define INF (1 << 30)
#define MOD 1000000007
using namespace std;
typedef long long ll;

ll N, graph[MAX_N][MAX_N], dp[MAX_N];
bool is_edge[MAX_N][MAX_N], dag[MAX_N][MAX_N], is_checked[MAX_N];

void bfs(int u) {
    queue<int> Q;
    Q.push(u);
    while (!Q.empty()) {
        int now_u = Q.front();
        Q.pop();
        for (int i = 0; i < N; i++) {
            if (now_u != i && dag[now_u][i]) {
                dp[i] = ((dp[i] % MOD) + (dp[now_u] % MOD)) % MOD;
                if (!is_checked[i]) {
                    Q.push(i);
                    is_checked[i] = true;
                }
            }
        }
    }
    return;
}

int main() {
    int a, b, M, x, y;
    cin >> N >> a >> b >> M;
    a--, b--;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            graph[i][j] = (i == j ? 0 : INF);
            dag[i][j] = false;
            is_edge[i][j] = false;
        }
    }
    for (int i = 0; i < M; i++) {
        cin >> x >> y;
        x--, y--;
        graph[x][y] = graph[y][x] = 1;
        is_edge[x][y] = is_edge[y][x] = true;
    }
    // 頂点間の最短経路導出
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k]);
            }
        }
    }
    // 頂点aを始点とするDAGを作成
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (is_edge[i][j] && graph[a][i] + 1 == graph[a][j]) dag[i][j] = true;
        }
    }
    // 動的計画法で最短経路をカウント
    for (int i = 0; i < N; i++) {
        dp[i] = 0;
        is_checked[i] = false;
    }
    dp[a] = 1;
    bfs(a);
    cout << dp[b] << endl;
    return 0;
}

Submission Info

Submission Time
Task C - 正直者の高橋くん
User hitorizuki
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1897 Byte
Status AC
Exec Time 3 ms
Memory 384 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 32
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 AC 1 ms 256 KB
subtask0_sample_02.txt AC 1 ms 256 KB
subtask1_01.txt AC 2 ms 384 KB
subtask1_02.txt AC 2 ms 384 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 2 ms 384 KB
subtask1_05.txt AC 2 ms 384 KB
subtask1_06.txt AC 1 ms 256 KB
subtask1_07.txt AC 1 ms 256 KB
subtask1_08.txt AC 1 ms 256 KB
subtask1_09.txt AC 1 ms 256 KB
subtask1_10.txt AC 1 ms 256 KB
subtask1_11.txt AC 2 ms 384 KB
subtask1_12.txt AC 2 ms 384 KB
subtask1_13.txt AC 2 ms 384 KB
subtask1_14.txt AC 2 ms 384 KB
subtask1_15.txt AC 2 ms 384 KB
subtask1_16.txt AC 2 ms 384 KB
subtask1_17.txt AC 2 ms 384 KB
subtask1_18.txt AC 2 ms 384 KB
subtask1_19.txt AC 2 ms 384 KB
subtask1_20.txt AC 2 ms 384 KB
subtask1_21.txt AC 2 ms 384 KB
subtask1_22.txt AC 2 ms 384 KB
subtask1_23.txt AC 2 ms 384 KB
subtask1_24.txt AC 2 ms 384 KB
subtask1_25.txt AC 2 ms 384 KB
subtask1_26.txt AC 2 ms 384 KB
subtask1_27.txt AC 2 ms 384 KB
subtask1_28.txt AC 3 ms 384 KB
subtask1_29.txt AC 1 ms 256 KB
subtask1_30.txt AC 1 ms 256 KB