Submission #2551353


Source Code Expand

#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 Info

Submission Time
Task A - 足し算
User hashmup
Language C++14 (Clang 3.8.0)
Score 0
Code Size 1438 Byte
Status WA
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
WA × 2
WA × 10
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
Case Name Status Exec Time Memory
subtask0_sample_01.txt WA 1 ms 256 KB
subtask0_sample_02.txt WA 1 ms 256 KB
subtask1_01.txt WA 1 ms 256 KB
subtask1_02.txt WA 1 ms 256 KB
subtask1_03.txt WA 1 ms 256 KB
subtask1_04.txt WA 1 ms 256 KB
subtask1_05.txt WA 1 ms 256 KB
subtask1_06.txt WA 1 ms 256 KB
subtask1_07.txt WA 1 ms 256 KB
subtask1_08.txt WA 1 ms 256 KB