Advertisement
Saleh127

UVA 1203 / Live Archive 3135 - Priority Queue

Oct 25th, 2021
1,010
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-10-26-00.20.36
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define nl '\n'
  10.  
  11. int main()
  12. {
  13.    ios_base::sync_with_stdio(0);
  14.    cin.tie(0);cout.tie(0);
  15.  
  16.  
  17.    string s;
  18.  
  19.    ll n,m,i,j,k,l;
  20.  
  21.    priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,greater<pair<ll,pair<ll,ll>>>>q;
  22.  
  23.    while(cin>>s && s[0]!='#')
  24.    {
  25.         cin>>n>>m;
  26.         q.push({m,{n,m}});
  27.    }
  28.  
  29.    cin>>k;
  30.  
  31.    while(k--)
  32.    {
  33.         auto d=q.top();
  34.         q.pop();
  35.  
  36.         cout<<d.second.first<<endl;
  37.  
  38.         i=d.second.first;
  39.         j=d.second.second;
  40.         l=d.first+d.second.second;
  41.  
  42.         q.push({l,{i,j}});
  43.    }
  44.  
  45.    return 0;
  46. }
  47.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement