AtCoder Beginner Contest 021

Submission #2374443

Source codeソースコード

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
using pi = pair<int,int>;

const int MAX = 101;
const int INFTY = 2e9;
const int WHITE = 1;
const int GRAY = 2;
const int BLACK = 3;
const int MOD = 1e9+7;

pi dist[MAX];
int G[MAX][MAX];
int color[MAX];

int N;

int bfs(int a, int b){
    for(int i=0;i<N;i++){
        dist[i].first = INFTY;
        dist[i].second = 0;
        color[i] = WHITE;
    }
    dist[a].first = 0;
    dist[a].second = 1;
    color[a] = BLACK;
    queue<int> Q;
    Q.push(a);

    while(!Q.empty()){
        int u = Q.front(); Q.pop();
        color[u] = BLACK;
        for(int v=0;v<N;v++){
            if(G[u][v] == 0) continue;
            if(color[v] == BLACK) continue;
            if(dist[v].first > dist[u].first + 1){
                dist[v].first = dist[u].first + 1;
                dist[v].second = dist[u].second;
                Q.push(v);
                color[v] = GRAY;
            }else if(dist[v].first == dist[u].first + 1){
                (dist[v].second += dist[u].second) %= MOD;
                color[v] = GRAY;
            }
        }
    }
    return dist[b].second;
}

int main(){
    cin >> N;
    int a,b; cin >> a >> b;
    a--; b--;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            G[i][j] = 0;
        }
    }
    int M; cin >> M;
    for(int i=0;i<M;i++){
        int x,y; cin >> x >> y;
        x--; y--;
        G[x][y] = 1; G[y][x] = 1;
    }

    cout << bfs(a,b)%MOD << endl;

    return 0;
}

Submission

Task問題 C - 正直者の高橋くん
User nameユーザ名 okechan
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1576 Byte
File nameファイル名
Exec time実行時間 1 ms
Memory usageメモリ使用量 256 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample_01.txt,subtask0_sample_02.txt
All 100 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask0_sample_01.txt AC 1 ms 256 KB
subtask0_sample_02.txt AC 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 1 ms 256 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 1 ms 256 KB
subtask1_12.txt AC 1 ms 256 KB
subtask1_13.txt AC 1 ms 256 KB
subtask1_14.txt AC 1 ms 256 KB
subtask1_15.txt AC 1 ms 256 KB
subtask1_16.txt AC 1 ms 256 KB
subtask1_17.txt AC 1 ms 256 KB
subtask1_18.txt AC 1 ms 256 KB
subtask1_19.txt AC 1 ms 256 KB
subtask1_20.txt AC 1 ms 256 KB
subtask1_21.txt AC 1 ms 256 KB
subtask1_22.txt AC 1 ms 256 KB
subtask1_23.txt AC 1 ms 256 KB
subtask1_24.txt AC 1 ms 256 KB
subtask1_25.txt AC 1 ms 256 KB
subtask1_26.txt AC 1 ms 256 KB
subtask1_27.txt AC 1 ms 256 KB
subtask1_28.txt AC 1 ms 256 KB
subtask1_29.txt AC 1 ms 256 KB
subtask1_30.txt AC 1 ms 256 KB