青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

pku 3635

2009年8月1日

題目鏈接:PKU 3635 Full Tank ?
  
題目分類:一道有趣的bfs(有點難度)

題目分析與算法原型

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

 2. 假設彈出的元素對應的是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]),相應的元素入隊列.


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表示堆元素的個數,從0開始編號,從h開始往下調整
 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開始往上調整
 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 閱讀(1593) 評論(2)  編輯 收藏 引用

評論

# re: pku 3635 2009-08-01 16:12 Vincent

=.=最短路徑吧...O(n^2)?  回復  更多評論   

# re: pku 3635 2009-08-04 17:25 付翔

不錯   回復  更多評論   


只有注冊用戶登錄后才能發表評論。
網站導航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            久久午夜影视| 亚洲电影免费观看高清完整版| 国产日产欧美精品| 国产精品人人做人人爽| 国产精品视频免费在线观看| 国产一区二区日韩精品欧美精品| 国产一区二区三区免费在线观看| 国产在线精品自拍| 亚洲人成在线播放网站岛国| 日韩一级二级三级| 亚洲嫩草精品久久| 美女露胸一区二区三区| 亚洲美女黄网| 久久九九热re6这里有精品| 欧美激情久久久久| 国产麻豆91精品| 亚洲国产小视频| 亚洲欧美在线视频观看| 欧美成人官网二区| 一区二区三区欧美激情| 久久人人爽人人爽| 欧美天堂在线观看| 亚洲电影天堂av| 性欧美大战久久久久久久免费观看| 猫咪成人在线观看| 亚洲一区日韩| 亚洲一区日韩在线| 很黄很黄激情成人| 一区免费观看| 亚洲一区二区黄色| 六十路精品视频| 一区二区三区av| 欧美成人69| 国产一区二区0| 亚洲男人影院| 亚洲激情不卡| 久久另类ts人妖一区二区| 国产精品女主播| 一本色道久久综合亚洲二区三区| 麻豆成人综合网| 亚洲欧美另类中文字幕| 欧美精品一区二区在线观看| 136国产福利精品导航网址应用| 欧美一区二区视频观看视频| 中日韩高清电影网| 欧美精品在线视频| 亚洲另类视频| 亚洲第一黄色| 欧美成人激情视频| 亚洲国产专区| 亚洲国产精品久久久久婷婷884 | 永久域名在线精品| 欧美一区二区三区免费视| 99re66热这里只有精品4 | 在线精品在线| 欧美a级一区二区| 欧美一区二区视频97| 国产伦精品一区二区三区照片91 | 日韩视频永久免费| 亚洲二区在线视频| 欧美激情按摩在线| 一本色道久久精品| 亚洲免费黄色| 国产精品videossex久久发布| 亚洲免费观看视频| 日韩一本二本av| 国产精品欧美激情| 久久国产一区| 久久亚洲精品欧美| 亚洲美女色禁图| 夜夜嗨av一区二区三区中文字幕| 欧美视频亚洲视频| 欧美一区三区三区高中清蜜桃| 欧美一级免费视频| 亚洲国产成人精品女人久久久| 亚洲国产免费看| 欧美日韩性生活视频| 最新国产成人在线观看| 欧美电影在线免费观看网站| 9国产精品视频| 亚洲一区国产视频| 激情欧美一区| 亚洲欧洲视频| 国产欧美一区二区精品性| 久久精品女人的天堂av| 美女日韩在线中文字幕| 在线视频精品一| 小黄鸭视频精品导航| 亚洲国产一区二区三区在线播| 99国产精品久久久| 国产日本亚洲高清| 亚洲激情婷婷| 国产在线播精品第三| 亚洲毛片一区| 激情五月综合色婷婷一区二区| 亚洲日本aⅴ片在线观看香蕉| 国产欧美精品日韩| 欧美激情一区二区| 国产欧美日韩| 亚洲免费观看高清完整版在线观看熊| 国产日韩欧美日韩大片| 亚洲国产精品久久久久婷婷884| 国产麻豆9l精品三级站| 亚洲精品在线观看免费| 国产一区二区在线观看免费播放| 亚洲激情偷拍| 樱花yy私人影院亚洲| 亚洲影音先锋| 夜夜嗨av一区二区三区免费区| 欧美在线国产| 欧美怡红院视频一区二区三区| 欧美区二区三区| 欧美好骚综合网| 一区二区亚洲精品| 午夜精品在线| 亚洲欧美亚洲| 欧美视频免费| 99re66热这里只有精品3直播 | 在线精品视频一区二区三四| 午夜精品免费在线| 亚洲欧美日韩一区在线| 欧美激情偷拍| 亚洲欧洲一区二区三区| 亚洲精品123区| 久久永久免费| 欧美成ee人免费视频| 黄色国产精品| 久久久久久网址| 麻豆精品网站| 亚洲国产激情| 免费不卡在线观看av| 免费高清在线视频一区·| 国内外成人免费视频| 欧美亚洲一区二区在线观看| 久久精品首页| 国产曰批免费观看久久久| 久久精品91久久香蕉加勒比| 久久久99国产精品免费| 国产一二三精品| 久久久一二三| 亚洲国产精品va在线看黑人动漫 | 1769国产精品| 久久综合九色综合欧美狠狠| 老色批av在线精品| 极品尤物久久久av免费看| 久久国产色av| 另类综合日韩欧美亚洲| 亚洲国产精品国自产拍av秋霞| 久久亚洲一区| 亚洲人成啪啪网站| 亚洲综合色丁香婷婷六月图片| 国产精品免费看| 久久aⅴ国产紧身牛仔裤| 蜜桃久久精品乱码一区二区| 亚洲国产日韩在线一区模特| 欧美肥婆bbw| 亚洲综合三区| 欧美成人国产va精品日本一级| 亚洲片在线观看| 国产精品成av人在线视午夜片| 欧美亚洲视频在线看网址| 欧美 日韩 国产 一区| 亚洲美女在线看| 国产精品一区二区在线观看| 久久综合色8888| 中文精品在线| 欧美成年人网| 亚洲欧美www| 亚洲国产精品一区二区久 | 欧美暴力喷水在线| 亚洲少妇中出一区| 免费欧美在线| 午夜伦理片一区| 最新日韩中文字幕| 国产欧美日韩高清| 欧美日韩成人免费| 久久精品国产综合精品| 一区二区三区鲁丝不卡| 欧美大片在线观看一区| 香蕉久久a毛片| 亚洲精品永久免费| 国模精品娜娜一二三区| 国产精品白丝黑袜喷水久久久| 免费观看成人鲁鲁鲁鲁鲁视频| 午夜精品福利视频| 一区二区三区国产在线观看| 欧美成人精品| 久久久久久国产精品一区| 亚洲性视频网站| 99re6热只有精品免费观看| 在线观看日韩欧美| 国产日韩欧美一区| 国产精品福利网站| 欧美日韩精品一本二本三本| 麻豆精品在线视频| 久久激情视频久久| 亚洲欧美一区二区视频| 一区二区三区你懂的| 亚洲精品国产精品国自产在线| 女女同性精品视频|