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