NBOJ 1186 Get the Width 最短路

  题意：求二叉树的宽度
   思路：这道题解法比较多了，可以搜索，也可以用最短路。用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; 
} 

 作者：wmn_wmn