Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define mod 1000000007
- #define ll long long
- #define N 105
- #define all(v) v.begin(),v.end()
- #define pii pair<int,int>
- #define piii pair<int,pii>
- #define print(x) cout << #x << "=" << x << "\t";
- #define newline cout << endl;
- int n;
- char s[N][N];
- int k;
- vector<int> v;
- int ff;
- int ss;
- int dist[N][N];
- vector<int> ans;
- void shortestPath(int id) {
- queue<int> q;
- bool h[N] = {0};
- q.push(id);
- h[id] = true;
- while (!q.empty()) {
- int top = q.front();
- q.pop();
- for(int i=1;i<=n;i++)
- if (s[top][i] == '1' && !h[i]) {
- dist[id][i] = dist[id][top] + 1;
- q.push(i);
- h[i] = true;
- }
- }
- }
- int main() {
- //ios::sync_with_stdio(false); cin.tie(NULL);
- scanf("%d", &n);
- for(int i=1;i<=n;i++)
- scanf("%s", s[i] + 1);
- scanf("%d", &k);
- v.resize(k);
- for(int i=0;i<k;i++)
- scanf("%d", &v[i]);
- ff = 0;
- ss = *v.rbegin();
- for(int i=1;i<=n;i++)
- shortestPath(i);
- ans.push_back(v[0]);
- for(int i=1;i<k;i++) {
- if (dist[v[ff]][v[i]] < i - ff) {
- ans.push_back(v[i - 1]);
- ff = i - 1;
- i--;
- }
- }
- ans.push_back(v[k - 1]);
- printf("%d\n", (int)ans.size());
- for(auto u : ans)
- printf("%d ", u);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement