Самый длинный путь в дереве - Spoj

Question

IDK, что не так с моим algo. Предоставление WA

Я использую Dijkstra, чтобы найти расстояние от всего узла от начального узла, а затем распечатать максимальное расстояние.

Ссылка: http://www.spoj.com/problems/PT07Z/

#define REP(i,n) for(int i=0;i<n;i++) 
#define FOR(i,start,end) for(int i=start;i<end;i++) 
#define pii pair< int, int > 

struct comp { 
    bool operator() (const pii &a, const pii &b) { 
     return a.second > b.second; 
    } 
}; 
priority_queue< pii ,vector<pii>, comp > Q; 
#define Size 10009 
vector<pii > G[Size]; 
int D[Size],Visited[Size]; 
int main() { 
    int n,m,s=1,t,a,b,p,q,d; 
    scanf("%d",&t); 
    REP(i, t-1) { 
     scanf("%d %d",&a,&b); 
     G[a].push_back(pii(b, 1)); 
     G[b].push_back(pii(a, 1)); 
    } 
    REP(i, t+2){D[i]=1000000;Visited[i]=0;} 
    D[s]=0; 
    Q.push(pii(s,0)); 
    while (!Q.empty()) { 
     a=Q.top().first; 
     Q.pop(); 
     if (Visited[a]) continue; 
     m=G[a].size(); 
     REP(i, m){ 
      p=G[a][i].first; 
      if (!Visited[p] && D[a]+1<D[p]) { 
       D[p]=D[a]+1; 
       Q.push(pii(p,D[p])); 
      } 
     } 
     Visited[a]=1; 
    } 
    m=0; 
    FOR(i, 1, t+1) if(D[i]>m && D[i]!=1000000) m=D[i]; 
    printf("%d\n",m); 
    return 0; 
} 

Answer 1

вам не нужно использовать dijsktra для этой проблемы, как края не взвешены.

Эта проблема связана с: "Find Tree Diameter", которые вы можете легко решить:

• Начать с узла А и запустить BFS.
• Теперь возьмите самый удаленный узел от A (позвоните на него B) и запустите другой BFS из своего.
• затем возьмите самый удаленный узел из B (позвоните на C). самым длинным расстоянием в дереве является расстояние между B и C.

Надеюсь, это помогло.