• <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 閱讀(1574) 評論(2)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    


            

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

            




            






            

				
				

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

            

					

            導航
            

					

            統(tǒng)計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



99国产精品久久|
99久久国产精品免费一区二区|
亚洲伊人久久大香线蕉苏妲己
|
久久久久久A亚洲欧洲AV冫|
久久国产视屏|
亚洲国产精品久久久天堂|
日本道色综合久久影院|
久久国产免费直播|
国产精品一区二区久久精品无码|
一本久久知道综合久久|
国产精品99久久精品|
少妇熟女久久综合网色欲|
久久久中文字幕|
久久精品国产清自在天天线|
99久久精品免费看国产免费|
亚洲国产精品久久久天堂|
久久一区二区三区免费|
狠狠狠色丁香婷婷综合久久俺|
亚洲七七久久精品中文国产|
国产亚洲精久久久久久无码|
婷婷国产天堂久久综合五月|
精品国产91久久久久久久a|
久久久久人妻精品一区|
久久人人青草97香蕉|
久久久精品视频免费观看|
久久91精品国产91久久户|
久久综合给合久久狠狠狠97色|
亚洲国产成人精品久久久国产成人一区二区三区综
|
精品久久久久久无码专区|
国产精品久久久香蕉|
亚洲国产一成久久精品国产成人综合
|
九九热久久免费视频|
久久国产精品99精品国产987|
久久无码人妻一区二区三区|
亚洲va中文字幕无码久久
|
国内精品人妻无码久久久影院|
中文字幕无码精品亚洲资源网久久
|
久久久久久久综合狠狠综合|
久久久黄色大片|
久久精品免费一区二区|
欧美日韩久久中文字幕|