Getting WA in Spoj problen:-BENEFACT — The Benefactor

Правка en2, от VIKRAM91, 2018-05-24 13:42:08

I am doing BENEFACT — The Benefactor.

I am using 2-time BFS method to calculate the longest path. Because here cost is associated with every edge so I am doing 2 times Dijkstra instead of 2 times BFS. But I am getting WA.

Can Anyone tell me Why I am getting WA?

Here is my code:-

#include<bits/stdc++.h>
  using namespace std;
  vector<pair<int,int> > adj[50000+5];
  pair<int,int> dijkstra(int x,int n){
      bool vis[n+1];
      int dist[n+1];
      for(int i=0;i<=n;i++){
          dist[i]=1000000;
          vis[i]=false;
      }
      dist[x]=0;
      multiset<pair<int,int> >s;
      s.insert({0,x});
      while(!s.empty()){
          pair<int,int> p=*s.begin();
          s.erase(s.begin());
          int x=p.second;
          int wei=p.first;
          if(vis[x])
              continue;
          vis[x]=true;
          for(int i=0;i<adj[x].size();i++){
              int e=adj[x][i].first;
              int w=adj[x][i].second;
              if(dist[x]+w<dist[e]){
                   dist[e]=dist[x]+w;
                   s.insert({dist[e],e});
              }
          }
      }
      int node,weight=0;
      for(int i=1;i<=n;i++){
          if(dist[i]>weight){
              node=i;
              weight=dist[i];
          }
      }
      return make_pair(node,weight);
  }

  int longestPath(int n){
      pair<int,int> t1,t2;
      t1=dijkstra(1,n);
      t2=dijkstra(t1.first,n);
      return t2.second;
  }

  int main(){
      int t;
      cin>>t;
      while(t--){
          int n;
          cin>>n;
          for(int i=0;i<=n;i++)
              adj[i].clear();
          int a,b,l;
          for(int i=0;i<n-1;i++){
              cin>>a>>b>>l;
              adj[a].push_back({b,l});
              adj[b].push_back({a,l});
          }
          cout<<longestPath(n)<<endl;
      }
      return 0;
  }
Теги spoj, dijkstra, #graph, longest path

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский VIKRAM91 2018-05-24 15:26:55 2187
en2 Английский VIKRAM91 2018-05-24 13:42:08 16
en1 Английский VIKRAM91 2018-05-24 13:39:17 2248 Initial revision (published)