登 录
http://acm.pku.edu.cn/JudgeOnline/problem?id=2263
hash + dijkstra
第一次用hash,据说某某学长在面试的时候写了个楼天成的hash函数,面试官二话不说,直接拉人~~
#include <cstdlib><br /> #include <iostream></p> <p>using namespace std;</p> <p>const int N =202;<br /> const int inf = 0x3fffffff;<br /> //一个比较大的质数，数组只开了202，而hash地址开到了99991。。。~~<br /> const int prim = /*99991*/203;</p> <p>int s,t;<br /> int a[N][N];//city之间的距离<br /> //所有hash地址为ha的关键字连成一个链表,hash[ha]指向这个链表头结点（或者尾结点）<br /> int hash[prim];//hash链接表<br /> int n,r;<br /> struct Str<br /> {<br /> char ch[31];<br /> int next;//记录有冲突的同义词~~<br /> }str[N];</p> <p>/**********************************************<br /> *将一个字符串的数组中的每个元素依次按前四位与上一个元素的低四位相与组成一个长整形,<br /> *如果长整的高四位大于零，那么就将它折回再与长整的低四位相异或.<br /> *这样最后得到的长整对HASH表长取余，得到在HASH中的位置.<br /> **********************************************/<br /> int ELFhash(char *key)<br /> {<br /> unsigned long h =0;<br /> while(*key)<br /> {<br /> h =(h<<4)+*key++;<br /> unsigned long g = h & 0xf0000000;<br /> //如果最高的四位不为0，则说明字符多余7个，如果不处理，再加第九个字符时，第一个字符会被移出，因此要有如下处理。<br /> //该处理，如果对于字符串(a-z 或者A-Z)就会仅仅影响5-8位，否则会影响5-31位，因为C语言使用的算数移位.(右移的时候用符号位填充)<br /> if(g) h ^= g >>24;<br /> //清空28-31位<br /> h &= ~g;<br /> }<br /> return h % prim;<br /> }</p> <p>int count;</p> <p>int GetID(char *u)<br /> {<br /> //根据字符串获取他的不重复id号<br /> int ha = ELFhash(u);<br /> int j = hash[ha];<br /> while(j)<br /> {<br /> //搜索hash链接表，遍历所有同义词<br /> if(strcmp(str[j].ch,u) ==0)<br /> {<br /> return j;<br /> }<br /> j = str[j].next;<br /> }<br /> //如果没有找到，则重新分配id给u字符串<br /> strcpy(str[count].ch, u);<br /> //插入到头结点<br /> //str[count].next= hash[ha];<br /> //hash[ha] = count;<br /> //插入到尾结点<br /> str[hash[ha]].next = count;<br /> hash[ha] = count;<br /> count ++;<br /> return count-1;<br /> }</p> <p>int GetF(char *key)//根据0-9字符串转换成整形<br /> {<br /> int t =0;<br /> while(*key)<br /> {<br /> t *= 10;<br /> t += (*key++ - '0');<br /> }<br /> return t;<br /> }</p> <p>int d[N];//路径中最大路段距离<br /> bool b[N];//记录city是否已被遍历</p> <p>//贪心加dp数组记录最大值<br /> int Solve()//dijkstra<br /> {<br /> memset(d,-1,sizeof(d));<br /> memset(b,0,sizeof(b));<br /> d[s] =inf;<br /> b[s] = 1;<br /> int src =s;<br /> for(int i=1;i<n;i++)<br /> {<br /> //每扩展一个结点就更新一次d[]<br /> for(int j =1;j<=n;j++)<br /> {<br /> if(!b[j] && -1 !=a[src][j])<br /> {<br /> //到prev结点的路径的最大段与prev结点到cur结点的的距离,二者中选小的<br /> //再与当前记录的到cur结点的路径中的最大段中选最大的<br /> //以更新d[cur]<br /> d[j] =max(d[j],min(d[src],a[src][j]));<br /> }<br /> }<br /> //寻找下一个扩展结点<br /> int p = -1;<br /> for(int j =1;j<=n;j++)<br /> {<br /> if(!b[j] && d[j]> p)<br /> {<br /> src = j;<br /> p = d[j];<br /> }<br /> }<br /> if(src == t)<br /> break;<br /> b[src] =1;<br /> }<br /> return d[t];<br /> }</p> <p>int main(int argc, char *argv[])<br /> {<br /> int ct =1;<br /> while(scanf("%d %d",&n,&r) && (n || r))<br /> {<br /> printf("Scenario #%d/n",ct);<br /> char u[31],v[31],f[12];<br /> memset(hash,0,sizeof(hash));<br /> memset(a,-1,sizeof(a));<br /> count =1;<br /> for(int i =0;i< r;i++)<br /> {<br /> scanf("%s %s %s",u,v,f);<br /> int uid = GetID(u);<br /> int vid = GetID(v);<br /> int fr = GetF(f);<br /> a[uid][vid] =fr;<br /> a[vid][uid] =fr;<br /> }<br /> scanf("%s %s",u,v);<br /> s = GetID(u);//设置起点和终点<br /> t = GetID(v);<br /> printf("%d tons/n/n",Solve());<br /> ct ++;<br /> }<br /> system("PAUSE");<br /> return EXIT_SUCCESS;<br /> }<br />
抱歉!评论已关闭.