fork download
copy 
  1. #include<iostream>
  2. #include<list>
  3. #include<string.h>
  4.  
  5. using namespace std;
  6. #define MAXI 1000000000
  7.  
  8. class Graph{
  9.     int v;
  10.     list<pair<int,int> > *adj;
  11.  
  12.     void dfsUtil(int s,int *path);
  13.  
  14.     public:
  15.     Graph(int v);
  16.     void addEdge(int u,int v,int w);
  17.     void dfs(int s,int d);
  18. };
  19.  
  20. Graph::Graph(int v){
  21.   this->v=v;
  22.   adj= new list<pair<int,int> >[v+1];
  23. }
  24.  
  25. void Graph:: addEdge(int u,int v,int w){
  26.   adj[u].push_back(make_pair(v,w));
  27.   adj[v].push_back(make_pair(u,w));
  28. }
  29.  
  30.   void Graph::dfsUtil(int s,int *path){
  31.  
  32.            int cost;
  33.          list<pair<int,int> > ::iterator i;
  34.          for(i=adj[s].begin();i!=adj[s].end();i++){
  35.  
  36.             cost= path[s] | (*i).second;
  37.  
  38.             if(cost<path[(*i).first]){
  39.                 path[(*i).first]=cost;
  40.             dfsUtil((*i).first,path);
  41.             }
  42.          }
  43.   }
  44.  
  45.   void Graph::dfs(int s,int d){
  46.      bool *visited= new bool[v+1];
  47.      memset(visited,false,v+1);
  48.      int path[v+1];
  49.  
  50.    for(int i=0;i<v+1;i++){
  51.     path[i]=MAXI;
  52.    }
  53.      path[s]=0;
  54.  
  55.      dfsUtil(s,path);
  56.  
  57.      if(path[d]==MAXI)
  58.         cout << "-1" << endl;
  59.       else
  60.             cout << path[d] <<endl;
  61.  
  62.   }
  63.  
  64. int main(){
  65.  int n,m,temp,temp2,temp3;
  66.  cin >> n>>m;
  67.   Graph g(n);
  68.  
  69.   for(int i=0;i<m;i++){
  70.       cin >> temp>>temp2>>temp3;
  71.       g.addEdge(temp,temp2,temp3);
  72.   }
  73.  
  74.   cin >> temp>>temp2;
  75.     g.dfs(temp,temp2);
  76.  
  77.  return 0;
  78. }
  79.  
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/WDYFte
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!