Guest User

code

a guest
Jul 13th, 2020
269
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.54 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define X ios_base::sync_with_stdio(false); cin.tie(NULL);
  4. #define FIXED_FLOAT(x) std::fixed <<std::setprecision(2)<<(x)
  5.  
  6.  
  7. void __print(int x) {cerr << x;}
  8. void __print(long x) {cerr << x;}
  9. void __print(long long x) {cerr << x;}
  10. void __print(unsigned x) {cerr << x;}
  11. void __print(unsigned long x) {cerr << x;}
  12. void __print(unsigned long long x) {cerr << x;}
  13. void __print(float x) {cerr << x;}
  14. void __print(double x) {cerr << x;}
  15. void __print(long double x) {cerr << x;}
  16. void __print(char x) {cerr << '\'' << x << '\'';}
  17. void __print(const char *x) {cerr << '\"' << x << '\"';}
  18. void __print(const string &x) {cerr << '\"' << x << '\"';}
  19. void __print(bool x) {cerr << (x ? "true" : "false");}
  20.  
  21. template<typename T, typename V>
  22. void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
  23. template<typename T>
  24. void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
  25. void _print() {cerr << "]\n";}
  26. template <typename T, typename... V>
  27. void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
  28. #ifndef ONLINE_JUDGE
  29. #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
  30. #else
  31. #define debug(x...)
  32. #endif
  33.  
  34.  
  35. // long long p = 1e9+7;
  36.  
  37. typedef long long ll;
  38. typedef pair<ll,ll> pl;
  39. typedef vector<int> VI;
  40. typedef vector<pair<ll,ll>> VP;
  41. typedef vector<ll> VL;
  42. typedef vector<bool> VB;
  43.  
  44. // typedef pair<ll, ll> PL;
  45. typedef unordered_map<ll, ll> UMP;
  46. #define FOR(i,b) for(i=0;i<b;i++)
  47. #define pb push_back
  48. #define mp make_pair
  49.  
  50. // typedef  unordered_set<ll>;
  51.  
  52.  
  53. void printa(VI &x,ll n){
  54.     ll i;
  55.     FOR(i, n){
  56.         cout<<x[i]<<" ";
  57.     }
  58.     cout<<endl;
  59. }
  60.  
  61.  
  62. /////GLOABLS VARS
  63. ll MOD = 1e9+7;
  64. ll gmx = 1e5+7;
  65. VL fact(gmx, 1);
  66. //////FUNCTIONS
  67. // ll pow(ll val, ll deg)
  68. // {
  69. //     if (!deg)
  70. //         return 1 % MOD;
  71. //     if (deg & 1)
  72. //         return pow(val, deg - 1) * val % MOD;
  73. //     ll res = pow(val, deg >> 1);
  74. //     return (res * res) % MOD;
  75. // }
  76. ll powm(ll a, ll p) {
  77.     ll res = 1;
  78.     while(p) {
  79.         if(p & 1) {res = (res * a) % MOD;}
  80.         p /= 2;
  81.         a = (a * a) % MOD;
  82.     }
  83.     return res;
  84. }
  85. ll inv(ll r){
  86.     return powm(r, MOD-2)%MOD;
  87. }
  88. ll nCr(ll n, ll r){
  89.     ll tmp = fact[n-r]*fact[r];
  90.     tmp = tmp%MOD;
  91.     return (fact[n]*inv(tmp))%MOD;
  92. }
  93.  
  94.  
  95. int main(){
  96.       ios::sync_with_stdio(0);
  97.       cin.tie(0);
  98.     #ifndef ONLINE_JUDGE
  99.         freopen("test_input.txt", "r", stdin);
  100.         freopen("output.txt", "w", stdout);
  101.         #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
  102.     #endif
  103.     ll i,u,v,j,c;
  104.     ll n,m;
  105.     cin>>n>>m;
  106.     vector<VL> adj(n+1);
  107.     FOR(i,m){
  108.         cin>>u>>v;
  109.         adj[u].pb(v);
  110.     }
  111.     VL dist(n+1, -1);
  112.     VL pre(n+1, -1);
  113.     dist[1] = 0;
  114.     debug(adj[1],n,m);
  115.     queue <ll> q;
  116.     q.push(1);
  117.     while(q.size()>0){
  118.         ll e = q.front();q.pop();
  119.         // debug(e);
  120.         for(auto nb: adj[e]){
  121.             if(dist[nb]<dist[e]+1){
  122.                 dist[nb]  = dist[e]+1;
  123.                 pre[nb] = e;
  124.                 q.push(nb);
  125.             }
  126.         }
  127.     }
  128.     if(dist[n]==-1){
  129.         cout<<"IMPOSSIBLE\n";
  130.     }
  131.     else{
  132.         cout<<dist[n]+1<<'\n';
  133.         ll node =n;
  134.         VL tmp;
  135.         while(node!=-1){
  136.             tmp.pb(node);
  137.             node = pre[node];
  138.         }
  139.         for(i=0;i<tmp.size();i++){
  140.             cout<<tmp[tmp.size()-1-i]<<" ";
  141.         }
  142.     }
  143.  
  144.    
  145. }
Add Comment
Please, Sign In to add comment