cosenza987

Untitled

Aug 2nd, 2021
702
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Problem: E. The Classic Problem
  2. // Contest: Codeforces - Codeforces Round #265 (Div. 1)
  3. // Memory Limit: 768 MB
  4. // Time Limit: 5000 ms
  5. // Date / Time: 2021-08-02 14:37:14
  6. // Author: cosenza
  7. // всё что ни делается - всё к лучшему
  8. // check list -> long long, special cases, array size, mod (a*b%p*c%p not a*b*c%p  ,  (a-b+p)%p not a-b )
  9. //
  10. // Powered by CP Editor (https://cpeditor.org)
  11.  
  12. #include <bits/stdc++.h>
  13.  
  14. using namespace std;
  15.  
  16. const int mod = 1e9 + 7;
  17. const long long lmax = 0x3f3f3f3f3f3f3f3f;
  18.  
  19. int binexp(long long a, long long n) {
  20.     long long res = 1;
  21.     while(n) {
  22.         if(n & 1) {
  23.             (res *= a) % mod;
  24.         }
  25.          (a *= a) % mod;
  26.          n >>= 1;
  27.     }
  28.     return res % mod;
  29. }
  30.  
  31. priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, std::greater<pair<long long, long long>>> q;
  32.  
  33. int main() {
  34.     ios_base::sync_with_stdio(false);
  35.     cin.tie(0);
  36.     int n, m;
  37.     cin >> n >> m;
  38.     vector<pair<long long, long long>> adj[n + 7];
  39.     vector<pair<long long, long long>> path(n + 7, {-1, -1});
  40.     vector<long long> cost(n + 7, lmax);
  41.     while(m--) {
  42.         long long u, v, x;
  43.         cin >> u >> v >> x;
  44.         adj[u].push_back({v, x});
  45.         adj[v].push_back({u, x});
  46.     }
  47.     long long x, y;
  48.     cin >> x >> y;
  49.     q.push({0, x});
  50.     while(!q.empty()) {
  51.         auto p = q.top();
  52.         q.pop();
  53.         long long c = p.first, a = p.second;
  54.         if(cost[a] < c) {
  55.             continue;
  56.         }
  57.         for(auto k : adj[a]) {
  58.             long long b = k.first, d = k.second;
  59.             if(cost[b] > (d + c) % mod) {
  60.                 path[b] = {a, d};
  61.                 cost[b] = (d + c) % mod;
  62.                 q.push({cost[b], b});
  63.             }
  64.         }
  65.     }
  66.     if(path[y].first == -1) {
  67.         cout << -1 << "\n";
  68.         return 0;
  69.     }
  70.     vector<long long> pp;
  71.     long long v = y;
  72.     long long totcost = 0;
  73.     while(v != x) {
  74.         pp.push_back(v);
  75.         v = path[v].first;
  76.     }
  77.     pp.push_back(x);
  78.     reverse(pp.begin(), pp.end());
  79.     long long totc = 0;
  80.     for(int i = 1; i < pp.size(); i++) {
  81.         totc = (totc + binexp(2, path[pp[i]].second)) % mod;
  82.     }
  83.     cout << totc << "\n";
  84.     cout << pp.size() << "\n";
  85.     for(auto k : pp) {
  86.         cout << k << " ";
  87.     }
  88.     return 0;
  89. }
RAW Paste Data