Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Mar 28th, 2020 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include<stack>
  5. using namespace std;
  6.  
  7. typedef pair<int, int> ii;
  8. typedef vector<int> vi;
  9. typedef vector<ii> vii;
  10. vector<vii> AdjList;
  11. priority_queue< ii, vector<ii>, greater<ii> > pq;
  12. vi dist;
  13. vi pre;
  14. #define INF 1000000000
  15.  
  16. void dijkstra(int s){
  17. dist[s] = 0;
  18. pq.push(ii(0, s));
  19.  
  20. while (!pq.empty()) {
  21.  ii front = pq.top();
  22.  pq.pop();
  23.  int w = front.first;
  24.  int u = front.second;
  25.  if (w > dist[u]){
  26.     continue;
  27.  }
  28.  for (int j = 0; j < AdjList[u].size(); j++) {
  29.     ii v = AdjList[u][j];
  30.     if (dist[u] + v.second < dist[v.first]) {
  31.     dist[v.first] = dist[u] + v.second;
  32.     pq.push(ii(dist[v.first], v.first));
  33.         pre[v.first]=u;
  34.    }
  35.   }
  36.  }
  37. }
  38.  
  39. int main() {
  40.  
  41. int A, B, V, E, s, a, b, w;
  42. cin >>A>>B>> V >> E;
  43. AdjList.assign(V, vii());
  44. dist.assign(V, INF);
  45. pre.assign(V, 0);
  46. for (int i = 0; i < E; i++) {
  47.    cin >> a >> b >> w;
  48.    AdjList[a].push_back(ii(b, w));
  49.   }
  50.     dijkstra(A);
  51.     stack<int> path;  
  52.    
  53.   if (dist[B] != INF){
  54.     path.push(B);
  55.     cout << dist[B] << endl;
  56.     int p = pre[B];
  57.     while (p!=A){
  58.         path.push(p);
  59.         p = pre[p];
  60.     }
  61.      path.push(A);
  62.      while (!path.empty()){
  63.          cout << path.top() << " ";
  64.          path.pop();
  65.      }
  66.   }  
  67.   else
  68.       cout << "-1";
  69. return 0;
  70. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top