Submission #6418572
Source Code Expand
# include <algorithm> # include <iostream> # include <iterator> # include <vector> # include <string> # include <queue> # include <stack> # include <cmath> # include <set> using namespace std; const int mod = 1e9+7; typedef pair<int, int> p; int main() { int n, a, b; cin >> n >> a >> b; --a; --b; vector<vector<int>> dist(n); for (int i=0; i<n; ++i) { dist.at(i).resize(n); fill(dist.at(i).begin(), dist.at(i).end(), 1001001001); dist.at(i).at(i) = 0; } int m, x, y; cin >> m; vector<vector<int>> g(n), ng(n); // ng: new graph for (int i=0; i<m; ++i) { cin >> x >> y; --x; --y; dist.at(x).at(y) = 1; dist.at(y).at(x) = 1; g[x].push_back(y); g[y].push_back(x); } // Floyd-Warshall for (int k=0; k<n; ++k) { for (int i=0; i<n; ++i) { for (int j=0; j<n; ++j) { dist.at(i).at(j) = min(dist.at(i).at(j), dist.at(i)[k]+dist[k].at(j)); } } } vector<bool> used(n); fill(used.begin(), used.end(), false); priority_queue<p, vector<p>, greater<p>> queue; queue.push(make_pair(0, 0)); vector<int> ans(n); fill(ans.begin(), ans.end(), 0); ans.at(0) = 1; while(!queue.empty()) { p pair = queue.top(); queue.pop(); int node = pair.second; int cost = pair.first; if(used.at(node)) continue; for (int next_node: g.at(node)) { if (used.at(next_node)) continue; if (dist.at(a).at(next_node) == cost+1) { queue.push(make_pair(cost+1, next_node)); ans.at(next_node) += ans.at(node); ans.at(next_node) %= mod; } } used.at(node) = true; } for (int i=0; i<n; ++i) cout << " " << ans.at(i); cout << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 正直者の高橋くん |
User | himkt |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1912 Byte |
Status | WA |
Exec Time | 3 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, 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 |
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 | 3 ms | 256 KB |
subtask1_02.txt | WA | 3 ms | 256 KB |
subtask1_03.txt | WA | 1 ms | 256 KB |
subtask1_04.txt | WA | 3 ms | 256 KB |
subtask1_05.txt | WA | 3 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 |
subtask1_09.txt | WA | 1 ms | 256 KB |
subtask1_10.txt | WA | 1 ms | 256 KB |
subtask1_11.txt | WA | 3 ms | 256 KB |
subtask1_12.txt | WA | 3 ms | 256 KB |
subtask1_13.txt | WA | 3 ms | 256 KB |
subtask1_14.txt | WA | 3 ms | 256 KB |
subtask1_15.txt | WA | 3 ms | 256 KB |
subtask1_16.txt | WA | 3 ms | 256 KB |
subtask1_17.txt | WA | 3 ms | 256 KB |
subtask1_18.txt | WA | 3 ms | 256 KB |
subtask1_19.txt | WA | 3 ms | 256 KB |
subtask1_20.txt | WA | 3 ms | 256 KB |
subtask1_21.txt | WA | 3 ms | 256 KB |
subtask1_22.txt | WA | 3 ms | 256 KB |
subtask1_23.txt | WA | 3 ms | 256 KB |
subtask1_24.txt | WA | 3 ms | 256 KB |
subtask1_25.txt | WA | 3 ms | 256 KB |
subtask1_26.txt | WA | 3 ms | 256 KB |
subtask1_27.txt | WA | 3 ms | 256 KB |
subtask1_28.txt | WA | 3 ms | 256 KB |
subtask1_29.txt | WA | 2 ms | 256 KB |
subtask1_30.txt | WA | 1 ms | 256 KB |