• <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 3635
		
            
		
            2009年8月1日

            題目鏈接：PKU 3635 Full Tank ?
              
            題目分類：一道有趣的bfs（有點難度）

            題目分析與算法原型

                     題目大意是，給你n個城市（n最大可以到1000）以及每個城市對應(yīng)的油價，這些城市間有m條路徑及每條路徑對應(yīng)的所連接的兩個城市以及路徑的長度（每條路徑連接兩個城市）也告訴了你，給你一輛車，車的油箱儲備量也已知，最后給你剛才n個城市中的某兩個a和b，問你用給你的汽車從a能不能到達b，若能，怎么走才能使得你所花費的油錢最小(路徑每走一單位需要用1升油)，并輸出這個最小的花費..........
                    老實說，從看到這道題目開始的將近一整天時間里面我都沒有什么好的思路，知道是一道廣搜，但是還不是特別清楚買油的方式，最后參考了某位大牛前輩的思路，才有了一點眉目（哎，搜索太爛了，有待提高啊）。大致做法是定義一個數(shù)組dis[][],其中dis[i][j]代表汽車到達i號城市，且油箱里面還有j升油的時候的最小花費，創(chuàng)建一個最小堆維護（不用堆優(yōu)化鐵定超時，剛開始堆優(yōu)化沒寫好，貢獻了2次TLE），從隊列中取出最小花費的那個，然后以它作為節(jié)點擴展開來（注意，這道題目城市數(shù)比較大，采用鄰接表存儲比較好）..........
                     
                    具體做法如下：
             1.每次從隊列中彈出第一個元素，因為采用了最小堆維護，這樣可以確保彈出的元素一定是隊列中花費最小那個元素

             2. 假設(shè)彈出的元素對應(yīng)的是dij[C][L]（既是在C號城市，剩下L升汽油時的最小花費）然后我們每次只買一升油，此時所花費的錢算上剛才一共是dij[C][L]+price[C](price[C]代表C號城市的油價)，然后更新，取dij[C][L+1]=Min(dij[C][L+1],dij[C][L]+price[C]),新擴展的元素入隊列

            3.枚舉每個和C號城市相互鄰接的城市X,如果當前儲備的油L>=d(d為C到X的路徑長度)，說明可以開到X城市，此時油剩下L-d,然后更新，取dis[X][L-d]=Min(dis[X][L-d],dis[C][L]),相應(yīng)的元素入隊列.


            Code:

              1            #include<stdio.h>
              2#define INF 1000000000
              3#define len 1005
              4int map[len][len],price[len],cost[len][len],n,m,count;
              5int dis[len][105],flag[len][105];
              6struct node
              7{
              8    int city,fuel,money;
              9}            queue[1000000];
             10void down_min_heap(int n,int h)//n表示堆元素的個數(shù)，從0開始編號,從h開始往下調(diào)整
             11{
             12    int i=h,j=2*i+1;
             13    node temp=queue[i];
             14    while(j<n)
             15    {
             16        if(j<n-1&&queue[j].money>queue[j+1].money)j++;//若右孩子存在，且右孩子比較小，取右
             17        if(temp.money<queue[j].money)break;
             18        else
             19        {
             20            queue[i]=queue[j];
             21            i=j;
             22            j=2*i+1;
             23        }
             24    }
             25    queue[i]=temp;
             26}
             27void up_min_heap(int s)
             28{
             29    while (s>0&&queue[s].money<queue[(s-1)/2].money)     //從s開始往上調(diào)整
             30    { 
             31        node tt=queue[s];
             32        queue[s]=queue[(s-1)/2];
             33        queue[(s-1)/2]=tt;
             34        s = (s-1)/2; 
             35    }
             36}
             37node pop()
             38{
             39    node res=queue[0];
             40    queue[0]=queue[count-1];
             41    count--;
             42    down_min_heap(count,0);
             43    return res;
             44}
             45void push(int c,int f,int m)
             46{
             47    queue[count].city=c;
             48    queue[count].fuel=f;
             49    queue[count].money=m;
             50    count++;
             51    up_min_heap(count-1);
             52}
             53int bfs(int cap,int start,int end)
             54{
             55    int i,j;
             56    count =0;
             57    for(i=0;i<n;i++)
             58        for(j=0;j<=cap;j++)
             59            dis[i][j]=INF,flag[i][j]=0;
             60    
             61    push(start,0,0);
             62    dis[start][0] = 0; 
             63
             64    while (count>0)
             65    {
             66        node u=pop();
             67        int city=u.city,left=u.fuel;
             68        if (flag[city][left]) continue; 
             69        if (city==end) break; 
             70        if (left<cap && dis[city][left+1]>dis[city][left]+price[city])
             71        { 
             72            dis[city][left+1]=dis[city][left]+price[city]; 
             73            push(city, left+1, dis[city][left+1]); 
             74        }
             75        for (i=1; i<= map[city][0];i++) 
             76        { 
             77            int v=map[city][i], nc=cost[city][i]; 
             78            if (left>=nc && dis[v][left-nc]>dis[city][left])
             79            { 
             80                dis[v][left-nc]=dis[city][left]; 
             81                push(v,left-nc,dis[v][left-nc]); 
             82            }
             83        }
             84        flag[city][left] = 1; 
             85    }
             86    return dis[end][0]; 
             87}
             88int main()
             89{
             90    int i,q;
             91    while(scanf("%d%d",&n,&m)!=EOF)
             92    {
             93        for(i=0;i<n;i++)
             94        {
             95            scanf("%d",&price[i]);
             96            map[i][0]=0;
             97        }
             98        for(i=0;i<m;i++)             //采用鄰接表的方式存
             99        {
            100            int a,b,l;
            101            scanf("%d%d%d",&a,&b,&l);
            102            map[a][++map[a][0]]=b;
            103            cost[a][map[a][0]]=l;
            104            map[b][++map[b][0]]=a;
            105            cost[b][map[b][0]]=l;
            106        }
            107        scanf("%d",&q);
            108        for(i=0;i<q;i++)
            109        {
            110            int cap,start,end;
            111            scanf("%d%d%d",&cap,&start,&end);
            112            int res=bfs(cap,start,end);
            113            if(res<INF)printf("%d\n",res);
            114            else printf("impossible\n");
            115        }
            116    }
            117    return 1;
            118}
            119
            

		
            
			posted on 2009-08-01 16:02 蝸牛也Coding 閱讀(1573) 評論(2)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    


            

            評論
            
	
	
			
            
				# re: pku 3635
					
						2009-08-01 16:12
					
				Vincent
			
            
			
            
				=.=最短路徑吧...O(n^2)?  回復(fù)  更多評論
				  
			
            
		
			
            
				# re: pku 3635
					
						2009-08-04 17:25
					
				付翔
			
            
			
            
				不錯   回復(fù)  更多評論
				  
			
            
		

            




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2010年2月>
            
	
            日一二三四五六
            31123456
            78910111213
            14151617181920
            21222324252627
            28123456
            78910111213
            

            

					

            導航
            

					

            統(tǒng)計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



亚洲AV无码一区东京热久久|
日本人妻丰满熟妇久久久久久|
99久久精品午夜一区二区|
久久中文骚妇内射|
久久这里只有精品久久|
欧美国产成人久久精品|
亚洲av日韩精品久久久久久a|
国产精品一区二区久久精品|
久久精品夜色噜噜亚洲A∨|
精品久久久久久久久免费影院|
久久久久久无码Av成人影院|
久久久久人妻精品一区三寸蜜桃|
久久久久亚洲AV无码专区首JN|
9久久9久久精品|
一级做a爰片久久毛片看看|
久久久久人妻一区精品性色av|
久久九九免费高清视频|
久久大香香蕉国产|
波多野结衣久久精品|
91久久九九无码成人网站|
精品久久久久久中文字幕大豆网|
国产—久久香蕉国产线看观看
|
2021国产成人精品久久|
久久久久久精品免费免费自慰|
色综合久久天天综合|
97久久精品人妻人人搡人人玩|
久久国产免费直播|
欧洲国产伦久久久久久久|
久久国产精品免费一区二区三区|
久久精品国产99久久无毒不卡|
亚洲国产精品无码久久久不卡|
久久综合鬼色88久久精品综合自在自线噜噜
|
99久久精品国产麻豆|
午夜精品久久久久久久|
久久亚洲精品成人无码网站|
亚洲国产综合久久天堂
|
精品多毛少妇人妻AV免费久久|
久久久久成人精品无码中文字幕|
伊人久久大香线蕉av不卡|
久久久久久久久久久久久久|
精品久久亚洲中文无码|