转载pku 2263

转载：http://blog.csdn.net/GoOnDrift/archive/2010/09/12/5879411.aspx
hash + dijkstra

   1. #include <cstdlib>
   2. #include <iostream>
   3.
   4. using namespace std;
   5.
   6. const int N =202;
   7. const int inf = 0x3fffffff;
   8. //一个比较大的质数，数组只开了202，而hash地址开到了99991。。。~~
   9. const int prim = /*99991*/203;
  10.
  11. int s,t;
  12. int a[N][N];//city之间的距离
  13. //所有hash地址为ha的关键字连成一个链表,hash[ha]指向这个链表头结点（或者尾结点）
  14. int hash[prim];//hash链接表
  15. int n,r;
  16. struct Str
  17. {
  18.            char ch[31];
  19.            int next;//记录有冲突的同义词~~
  20. }str[N];
  21.
  22. /**********************************************
  23. *将一个字符串的数组中的每个元素依次按前四位与上一个元素的低四位相与组成一个长整形,
  24. *如果长整的高四位大于零，那么就将它折回再与长整的低四位相异或.
  25. *这样最后得到的长整对HASH表长取余，得到在HASH中的位置.
  26. **********************************************/
  27. int ELFhash(char *key)
  28. {
  29.         unsigned long h =0;
  30.         while(*key)
  31.         {
  32.                        h =(h<<4)+*key++;
  33.                         unsigned long g = h & 0xf0000000;
  34.                        //如果最高的四位不为0，则说明字符多余7个，如果不处理，再加第九个字符时，第一个字符会被移出，因此要有如下处理。
  35.         //该处理，如果对于字符串(a-z 或者A-Z)就会仅仅影响5-8位，否则会影响5-31位，因为C语言使用的算数移位.(右移的时候用符号位填充)
  36.                         if(g) h  ^= g >>24;
  37.                         //清空28-31位
  38.                        h &= ~g;
  39.          }
  40.         return h % prim;
  41. }
  42.
  43. int count;
  44.
  45. int GetID(char *u)
  46. {
  47.         //根据字符串获取他的不重复id号
  48.         int ha = ELFhash(u);
  49.        int j = hash[ha];
  50.         while(j)
  51.        {
  52.                     //搜索hash链接表，遍历所有同义词
  53.                     if(strcmp(str[j].ch,u) ==0)
  54.                     {
  55.                                                 return j;
  56.                      }
  57.                     j = str[j].next;
  58.        }
  59.     //如果没有找到，则重新分配id给u字符串
  60.        strcpy(str[count].ch, u);
  61.         //插入到头结点
  62.         //str[count].next= hash[ha];
  63.        //hash[ha] = count;
  64.        //插入到尾结点
  65.         str[hash[ha]].next = count;
  66.        hash[ha] = count;
  67.         count ++;
  68.        return count-1;
  69. }
  70.
  71. int GetF(char *key)//根据0-9字符串转换成整形
  72. {
  73.         int t =0;
  74.         while(*key)
  75.         {
  76.                        t *= 10;
  77.                         t += (*key++ - '0');
  78.          }
  79.          return t;
  80. }
  81.
  82. int d[N];//路径中最大路段距离
  83. bool b[N];//记录city是否已被遍历
  84.
  85. //贪心加dp数组记录最大值
  86. int Solve()//dijkstra
  87. {
  88.          memset(d,-1,sizeof(d));
  89.      memset(b,0,sizeof(b));
  90.         d[s] =inf;
  91.         b[s] = 1;
  92.         int src =s;
  93.         for(int i=1;i<n;i++)
  94.         {
  95.                     //每扩展一个结点就更新一次d[]
  96.                         for(int j =1;j<=n;j++)
  97.                         {
  98.                                       if(!b[j] && -1 !=a[src][j])
  99.                                      {
 100.                                                      //到prev结点的路径的最大段与prev结点到cur结点的的距离,二者中选小的
 101.                                                     //再与当前记录的到cur结点的路径中的最大段中选最大的
 102.                                                   //以更新d[cur]
 103.                                                   d[j] =max(d[j],min(d[src],a[src][j]));
 104.                                     }
 105.                         }
 106.                         //寻找下一个扩展结点
 107.          int p = -1;
 108.          for(int j =1;j<=n;j++)
 109.                         {
 110.                                        if(!b[j] && d[j]> p)
 111.                                         {
 112.                                                      src = j;
 113.                                                       p = d[j];
 114.                 }
 115.          }
 116.                         if(src == t)
 117.                                      break;
 118.                          b[src] =1;
 119.          }
 120.         return d[t];
 121. }
 122.
 123.
 124.
 125. int main(int argc, char *argv[])
 126. {
 127.         int ct =1;
 128.         while(scanf("%d %d",&n,&r) && (n || r))
 129.         {
 130.                              printf("Scenario #%d\n",ct);
 131.                              char u[31],v[31],f[12];
 132.                               memset(hash,0,sizeof(hash));
 133.                               memset(a,-1,sizeof(a));
 134.                              count =1;
 135.                              for(int i =0;i< r;i++)
 136.                              {
 137.                                            scanf("%s %s %s",u,v,f);
 138.                                           int uid = GetID(u);
 139.                                           int vid = GetID(v);
 140.                                           int fr = GetF(f);
 141.                                           a[uid][vid] =fr;
 142.                                            a[vid][uid] =fr;
 143.                               }
 144.                              scanf("%s %s",u,v);
 145.                               s = GetID(u);//设置起点和终点
 146.                               t = GetID(v);
 147.                               printf("%d tons\n\n",Solve());
 148.                               ct ++;
 149.         }
 150.         system("PAUSE");
 151.         return EXIT_SUCCESS;
 152. }