AtCoder Beginner Contest 021

Submission #2551358

Source codeソースコード

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
#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;
vector<int> G[MAX_N];
bool used[MAX_N];
int dist[MAX_N];
ll cnt[MAX_N];

void dijkstra(int x, int n) {
    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<G[p.second].size();i++) {
            if (!used[G[p.second][i]]) {
                dist[G[p.second][i]] = min(dist[G[p.second][i]], dist[p.second] + 1);
                pq.push(P(dist[G[p.second][i]], G[p.second][i]));
            }
        }
    }
}

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

int main() {
    int a, b, n, m, x, y;
    cin >> n;
    cin >> a >> b;
    cin >> m;
    for (int i=0;i<m;i++) {
        cin >> x >> y;
        x--;y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    a--;b--;
    memset(used, false, sizeof(used));
    dijkstra(a, n);
    cnt[a] = 1;
    memset(used, false, sizeof(used));
    count_path(a);
    cout << cnt[b] << endl;
}

Submission

Task問題 C - 正直者の高橋くん
User nameユーザ名 hashmup
Created time投稿日時
Language言語 C++14 (Clang 3.8.0)
Status状態 TLE
Score得点 0
Source lengthソースコード長 1731 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,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 4 ms 256 KB
subtask1_04.txt TLE
subtask1_05.txt TLE
subtask1_06.txt AC 1 ms 256 KB
subtask1_07.txt AC 2 ms 384 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 93 ms 2420 KB
subtask1_12.txt TLE
subtask1_13.txt AC 44 ms 1400 KB
subtask1_14.txt TLE
subtask1_15.txt TLE
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