程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> NBOJ 1186 Get the Width 最短路

NBOJ 1186 Get the Width 最短路

編輯：C++入門知識

題意：求二叉樹的寬度
思路：這道題解法比較多了，可以搜索，也可以用最短路。用dijkstra（）寫了一下，復習了一下dijkstra算法。

代碼：
[cpp]
#include <iostream>
#include <cstdio>
#include <string.h>
#include <vector>
#include <climits>
using namespace std;

#define CLR(arr,val) memset(arr,val,sizeof(arr))
int dis[20],cnt[20],numnode,map[20][20],visted[20];

int dijkstra(){
    CLR(visted,0);
    for(int i = 1;i <= numnode;++i)
        dis[i] = INT_MAX;
    dis[1] = 0;
    visted[1] = 1;
    int pos = 1;
    for(int i = 1;i <= numnode;++i){
        for(int j = 1;j <= numnode;++j){
            if(!visted[j] && map[pos][j] != INT_MAX && dis[pos]+map[pos][j] < dis[j]){
              dis[j] = dis[pos] + map[pos][j];
            }
        }
        int mmin = INT_MAX;
        for(int j = 1;j <= numnode;++j){
            if(!visted[j] && dis[j] < mmin){
              mmin = dis[j];
              pos = j;
            }
        }
        visted[pos] = 1;
    }
    int mmax = 0;
    for(int i = 1;i <= numnode;++i){
      cnt[dis[i]]++;
      if(cnt[dis[i]] > mmax)
          mmax = cnt[dis[i]];
    }
    return mmax;
}
int main(){
    //freopen("1.txt","r",stdin);
    int numcase;
    scanf("%d",&numcase);
    while(numcase--){
      int id,x,y;
      scanf("%d",&numnode);
      for(int i = 1;i <= numnode;++i)
          for(int j = 1;j <= numnode;++j)
              map[i][j] = INT_MAX;
      int numroot = numnode;
      while(numroot--){
        scanf("%d%d%d",&id,&x,&y);
        if(x != -1) map[id][x] = 1;
        if(y != -1) map[id][y] = 1;
      }
      CLR(cnt,0);
      int ans = dijkstra();
      printf("%d\n",ans);
    }
    return 0;
}