daily pastebin goal
53%
SHARE
TWEET

154-Journey

a guest Feb 22nd, 2019 50 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int INF=1000000000;
  4. typedef pair<int,int> pii;
  5. vector<bool> check(105000,false);
  6. vector<int> dis(105000,INF);
  7. vector<pii> G[105000];
  8. priority_queue<pii,vector<pii>,greater<pii>> Q;
  9. int mx;
  10. int main()
  11. {
  12.     int n,m,k;
  13.     scanf("%d%d%d",&n,&m,&k);
  14.     int a,b,c;
  15.     while(m--){
  16.         scanf("%d%d%d",&a,&b,&c);
  17.         G[a].push_back({c,b});
  18.         G[b].push_back({c,a});
  19.     }
  20.     dis[1]=0;
  21.     Q.push({0,1});
  22.     while(!Q.empty()){
  23.         int u=Q.top().second;
  24.         Q.pop();
  25.         if(dis[u]<=k && u>mx) mx=u;
  26.         if(check[u]) continue;
  27.         check[u]=true;
  28.         for(auto a:G[u]){
  29.             int v=a.second;
  30.             int w=a.first;
  31.             if(!check[v] && dis[v] > dis[u]+w){
  32.                 dis[v]=dis[u]+w;
  33.                 Q.push({dis[v],v});
  34.             }
  35.         }
  36.     }
  37.     printf("%d",mx);
  38.     return 0;
  39. }
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