fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int inPr[1002];
  4. int inPr1[1002];
  5. vector<pair<int,int>> a[1002];
  6. void prims(int source , int des,int t1,int t2){
  7. priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
  8. for(int i=0;i<1002;i++){
  9. inPr[i]=999999999;
  10. inPr1[i]=false;}
  11. //vector<int>parent(V+1,-1);
  12. //vector<int>key(V+1,100000000);
  13. pq.push(make_pair(0,source));
  14. //key[source]=0;
  15.  
  16. while(!pq.empty()){
  17.     pair<int,int> ss = pq.top();
  18.     int vv = ss.second;
  19.     int ww = ss.first;
  20.  
  21. if(vv==des) {cout<<"Yes"<<endl;return;}
  22.     pq.pop();
  23.     vector< pair<int, int> >::iterator itr = a[vv].begin();
  24.     while (itr != a[vv].end()){
  25.         int v = (*itr).second;
  26.         int w = (*itr).first;
  27.        // cout<<v<<endl;
  28.         if(w < t1  || ww>w) continue;
  29.         if(inPr[v]>w &&inPr1[v]==false ) {
  30.               //  cout<<"a"<<endl;
  31.             if(v==des && w <=t2) {cout<<"Yes"<<endl;return;}
  32.           else if(v==des) cout<<"No"<<endl;
  33.                 pq.push(make_pair(w,v));
  34.             inPr[v]=w;
  35.             inPr1[v]=true;
  36.            // parent[v]=vv;
  37.         }
  38.         itr++;
  39.     }
  40. }
  41. cout<<"No"<<endl;
  42. }
  43.  
  44. main()
  45. {
  46.     int E;
  47.     while(cin>>E){
  48. //            clr();
  49. for(int i=0;i<1002;i++){
  50. a[i].clear();}
  51. //a.clear();
  52.  
  53.  
  54.         for(int i=0;i<E;i++){
  55.             int x,y,t;//
  56.             cin>>x>>y>>t;
  57.             a[x].push_back(make_pair(t,y));
  58.             a[y].push_back(make_pair(t,x));
  59.         }
  60.         int Q;
  61.         cin>>Q;
  62.         for(int i=0;i<1001;i++) sort(a[i].begin(),a[i].end());
  63.         for(int i=0;i<Q;i++) {
  64.             int m, t1 , n ,t2;
  65.             cin>>m>>t1>>n>>t2;
  66.             prims(m,n,t1,t2);
  67.         }
  68.     }
  69.  
  70. }
  71.  
Success #stdin #stdout 0s 15280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3jdrjz
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!