• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        
			
			


			
            
				
					
	
            
		
            
			pku 2908
		
            
		
            2009年8月3日

            題目鏈接：PKU 2908 Quantum
              
            分類：bfs+堆優化

            題目分析與算法原型
                     這道題總的來說是一個廣度優先搜索，但是需要用最小堆進行優化（如果不用堆，呵呵，我沒試過，不過8成會TLE），每次從隊列中取隊頭元素進行擴展（由于是最小堆，保證了每次取出的元素是當前中花費最小的），需要注意的是，一個已經入過隊列的元素，還可以再入隊列，只要此時他的花費比上次入隊列時小就行，還要注意的一點是結束條件應該是當且隊列彈出的隊頭元素的關鍵值等于目標關鍵值，此時可以結束搜索，因為即使以后再次遇到該關鍵值的元素其花費肯定比現在的大，因為每次從隊頭開始擴展的元素都會比擴展他的父親元素的花費大，我就是這個退出條件沒搞好結果貢獻了n次的WA.............

            Code:

              1            #include<stdio.h>
              2#include<string.h>
              3char beg[25],end[25];
              4int n,l,p,w,count,mincost[1200000];
              5bool flag[1200000],finish;
              6struct node
              7{
              8    int cost,num;
              9    char s[25];
             10}            queue[1200000];
             11struct caozuo
             12{
             13    char s[25];
             14    int cost;
             15}            op[35];
             16int cal(char ss[])
             17{
             18    int i,res=0;
             19    for(i=0;i<l;i++)res+=(ss[i]-'0')<<(l-1-i);
             20    return res;
             21}
             22void down_min_heap(int n,int h)//n表示堆元素的個數，從0開始編號,從h開始往下調整
             23{
             24    int i=h,j=2*i+1;
             25    node temp=queue[i];
             26    while(j<n)
             27    {
             28        if(j<n-1&&queue[j].cost>queue[j+1].cost)j++;//若右孩子存在，且右孩子比較小，取右
             29        if(temp.cost<queue[j].cost)break;
             30        else
             31        {
             32            queue[i]=queue[j];
             33            i=j;
             34            j=2*i+1;
             35        }
             36    }
             37    queue[i]=temp;
             38}
             39void up_min_heap(int s)    //s表示最后一個的編號
             40{
             41    while (s>0&&queue[s].cost<queue[(s-1)/2].cost)     //從s開始往上調整
             42    { 
             43        node tt=queue[s];
             44        queue[s]=queue[(s-1)/2];
             45        queue[(s-1)/2]=tt;
             46        s=(s-1)/2; 
             47    }
             48}
             49void push(int x,int cost,char s[])
             50{
             51    queue[count].num=x;
             52    queue[count].cost=cost;
             53    strcpy(queue[count].s,s);
             54    count++;
             55    up_min_heap(count-1);
             56}
             57node pop()
             58{
             59    node res=queue[0];
             60    queue[0]=queue[count-1];
             61    count--;
             62    down_min_heap(count,0);
             63    return res;
             64}
             65void handle(int num,node x,int goal,int *ans)
             66{
             67    int i,k;
             68    node y=x;
             69    if(y.num==goal)
             70    {
             71        finish=true;
             72        *ans=y.cost;
             73        return ;
             74    }
             75    for(i=0;i<l;i++)
             76    {
             77        if(op[num].s[i]=='F')
             78        {
             79            if(y.s[i]=='0')y.s[i]='1';
             80            else y.s[i]='0';
             81        }
             82        else if(op[num].s[i]=='S')y.s[i]='1';
             83        else if(op[num].s[i]=='C')y.s[i]='0';
             84    }
             85    k=cal(y.s);
             86    if(!flag[k]||(flag[k]&&op[num].cost+y.cost<mincost[k]))
             87    {
             88        flag[k]=true;
             89        mincost[k]=op[num].cost+y.cost;
             90        push(k,op[num].cost+y.cost,y.s);
             91    }
             92}
             93int bfs(char a[],char b[])
             94{
             95    int r1=cal(a),r2=cal(b),i,ans;
             96    node tt;
             97    queue[0].num=r1;
             98    queue[0].cost=0;
             99    strcpy(queue[0].s,a);
            100    count=1;
            101    flag[r1]=true;
            102    mincost[r1]=0;
            103    while(count>0)
            104    {
            105        tt=pop();
            106        for(i=0;i<p&&!finish;i++)handle(i,tt,r2,&ans);
            107        if(finish)return ans;
            108    }
            109    return -1;
            110}
            111int main()
            112{
            113    int i;
            114    scanf("%d",&n);
            115    while(n--)
            116    {
            117        scanf("%d%d%d",&l,&p,&w);
            118        for(i=0;i<p;i++)scanf("%s %d",op[i].s,&op[i].cost);
            119        for(i=0;i<w;i++)
            120        {
            121            scanf("%s %s",beg,end);
            122            memset(flag,false,sizeof(flag));
            123            finish=false;
            124            int res=bfs(beg,end);
            125            if(res==-1)printf("NP");
            126            else printf("%d",res);
            127            if(i<w-1)printf(" ");
            128        }
            129        printf("\n");
            130    }
            131    return 1;
            132}
            133
            134
            135
            136
            

		
            
			posted on 2009-08-03 10:32 蝸牛也Coding 閱讀(181) 評論(0)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2009年8月>
            
	
            日一二三四五六
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345
            

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



人妻少妇久久中文字幕一区二区|
日本精品久久久久中文字幕|
久久99精品久久久久久水蜜桃
|
无码国内精品久久人妻|
欧美牲交A欧牲交aⅴ久久
|
精品国产一区二区三区久久久狼
|
亚洲七七久久精品中文国产|
免费精品久久久久久中文字幕|
午夜福利91久久福利|
国内精品久久久久影院优|
久久国产视频网|
狠狠干狠狠久久|
久久人人爽人人爽人人av东京热
|
亚洲人AV永久一区二区三区久久|
久久精品水蜜桃av综合天堂|
韩国三级中文字幕hd久久精品|
色综合久久综合中文综合网|
国产免费久久精品丫丫|
狠色狠色狠狠色综合久久|
久久九九兔免费精品6|
久久久久黑人强伦姧人妻|
久久精品国产69国产精品亚洲|
久久无码专区国产精品发布|
老司机午夜网站国内精品久久久久久久久
|
亚洲va中文字幕无码久久不卡|
久久人人爽人人爽人人片AV东京热|
久久精品国产亚洲AV嫖农村妇女|
伊人久久国产免费观看视频
|
亚洲精品乱码久久久久久自慰|
久久精品成人影院|
99久久精品国产综合一区|
久久免费精品一区二区|
国产精品久久久福利|
72种姿势欧美久久久久大黄蕉|
久久久精品人妻一区二区三区蜜桃|
久久久久亚洲AV综合波多野结衣|
久久99国产精品久久|
久久最近最新中文字幕大全|
久久综合久久久|
精品久久人人妻人人做精品|
久久精品?ⅴ无码中文字幕|