AtCoder Beginner Contest 021

Submission #2551353

Source codeソースコード

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const ll MOD = 1000000007;
const ll INF = 100000007;
const int MAX_N = 101;
bool G[MAX_N][MAX_N];
bool used[MAX_N];
int dist[MAX_N];
ll cnt[MAX_N];
int a, b, n, m, x, y;

void dijkstra(int x) {
    for(int i=0;i<n;i++) {
        dist[i] = INF;
    }
    priority_queue<P, vector<P>, greater<P> > pq;
    dist[x] = 0;
    pq.push(P(0, x));
    while (!pq.empty()) {
        P p = pq.top();pq.pop();
        used[p.second] = true;
        for (int i=0;i<n;i++) {
            if (i != p.second && G[p.second][i] && !used[i]) {
                dist[i] = min(dist[i], dist[p.second] + 1);
                pq.push(P(dist[i], i));
            }
        }
    }
}

void count_path(int x) {
    queue<int> q;
    q.push(x);
    while (!q.empty()) {
        int cur = q.front();q.pop();
        for (int i=0;i<n;i++) {
            if (G[cur][i] && dist[cur] + 1 == dist[i]) {
                cnt[i] = (cnt[i] + cnt[x]) % MOD;
                q.push(i);
            }
        }
    }
}

int main() {
    cin >> n;
    cin >> a >> b;
    cin >> m;
    for (int i=0;i<m;i++) {
        cin >> x >> y;
        G[x-1][y-1] = true;
        G[y-1][x-1] = true;
    }
    a--;b--;
    dijkstra(a);
    cnt[a] = 1;
    count_path(a);
    cout << cnt[b] << endl;
}

Submission

Task問題 A - 足し算
User nameユーザ名 hashmup
Created time投稿日時
Language言語 C++14 (Clang 3.8.0)
Status状態 WA
Score得点 0
Source lengthソースコード長 1438 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask0_sample_01.txt WA
subtask0_sample_02.txt WA
subtask1_01.txt WA
subtask1_02.txt WA
subtask1_03.txt WA
subtask1_04.txt WA
subtask1_05.txt WA
subtask1_06.txt WA
subtask1_07.txt WA
subtask1_08.txt WA