Advertisement
Guest User

Untitled

a guest
Aug 20th, 2019
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.42 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define mod 1000000007
  4. #define ll long long
  5. #define N 105
  6. #define all(v) v.begin(),v.end()
  7. #define pii pair<int,int>
  8. #define piii pair<int,pii>
  9. #define print(x) cout << #x << "=" << x << "\t";
  10. #define newline cout << endl;
  11.  
  12. int n;
  13. char s[N][N];
  14. int k;
  15. vector<int> v;
  16. int ff;
  17. int ss;
  18. int dist[N][N];
  19. vector<int> ans;
  20.  
  21. void shortestPath(int id) {
  22. queue<int> q;
  23. bool h[N] = {0};
  24. q.push(id);
  25. h[id] = true;
  26. while (!q.empty()) {
  27. int top = q.front();
  28. q.pop();
  29. for(int i=1;i<=n;i++)
  30. if (s[top][i] == '1' && !h[i]) {
  31. dist[id][i] = dist[id][top] + 1;
  32. q.push(i);
  33. h[i] = true;
  34. }
  35. }
  36. }
  37.  
  38. int main() {
  39. //ios::sync_with_stdio(false); cin.tie(NULL);
  40. scanf("%d", &n);
  41. for(int i=1;i<=n;i++)
  42. scanf("%s", s[i] + 1);
  43. scanf("%d", &k);
  44. v.resize(k);
  45. for(int i=0;i<k;i++)
  46. scanf("%d", &v[i]);
  47. ff = 0;
  48. ss = *v.rbegin();
  49.  
  50. for(int i=1;i<=n;i++)
  51. shortestPath(i);
  52.  
  53. ans.push_back(v[0]);
  54. for(int i=1;i<k;i++) {
  55. if (dist[v[ff]][v[i]] < i - ff) {
  56. ans.push_back(v[i - 1]);
  57. ff = i - 1;
  58. i--;
  59. }
  60. }
  61. ans.push_back(v[k - 1]);
  62.  
  63. printf("%d\n", (int)ans.size());
  64. for(auto u : ans)
  65. printf("%d ", u);
  66. return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement