• <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>

            USACO 3.2 Sweet Butter


            稀疏圖的多源最短路徑問題,用heap+disjktra解決。

            #include?<iostream>
            #include?
            <fstream>
            #include?
            <list>
            #include?
            <queue>

            using?namespace?std;

            ifstream?fin(
            "butter.in");
            ofstream?fout(
            "butter.out");

            #ifdef?_DEBUG
            #define?out?cout
            #define?in?cin
            #else
            #define?out?fout
            #define?in?fin
            #endif

            int?n,p,c;

            struct?edge{
            ????
            int?node;
            ????
            int?weight;
            ????edge(
            int?n,int?w):node(n),weight(w){
            ????}
            };

            struct?graph_node{
            ???list
            <edge>?adj;?
            };

            struct?pri_que_node{
            ????
            int?num;
            ????
            int?dist;
            ????pri_que_node(
            int?n,int?d):num(n),dist(d){
            ????};
            ????
            bool?operator<?(const?pri_que_node?&n2)?const{
            ????????
            return?dist>n2.dist;
            ????}
            };

            graph_node?graph[
            801];
            int?cow_place[801];
            int?shortest_path[801][801];

            void?get_shortest(int?n)
            {
            ????
            for(int?i=1;i<801;++i)
            ????????shortest_path[n][i]?
            =?INT_MAX;

            ????shortest_path[n][n]?=?0;
            ????priority_queue
            <pri_que_node>?pq;
            ????
            for(list<edge>::iterator?li?=?graph[n].adj.begin();
            ???????????????????li
            !=graph[n].adj.end();
            ???????????????????li
            ++){
            ????????pq.push(?pri_que_node(li
            ->node,li->weight)?);
            ????????shortest_path[n][li
            ->node]?=?li->weight;
            ????}

            ????
            while(?!pq.empty()?){
            ???????pri_que_node?node?
            =?pq.top();
            ???????pq.pop();

            ???????
            if(?node.dist>?shortest_path[n][node.num]?)
            ???????????
            continue;

            ???????shortest_path[n][node.num]?
            =?node.dist;

            ???????
            for(list<edge>::iterator?li?=?graph[node.num].adj.begin();
            ???????????????????li
            !=graph[node.num].adj.end();
            ???????????????????li
            ++){
            ???????????
            if(?node.dist+li->weight?<?shortest_path[n][li->node]?){
            ???????????????shortest_path[n][li
            ->node]?=?node.dist+li->weight;
            ???????????????pq.push(?pri_que_node(li
            ->node,?shortest_path[n][li->node])?);
            ???????????}
            ????????}
            ????}
            }

            void?solve()
            {
            ????
            in>>n>>p>>c;

            ????
            for(int?i=0;i<n;++i)
            ????????
            in>>cow_place[i];

            ????
            int?a,b,w;
            ????
            while(c--){
            ????????
            in>>a>>b>>w;
            ????????graph[a].adj.push_back(?edge(b,w)?);
            ????????graph[b].adj.push_back(?edge(a,w)?);
            ????}
            #ifdef?_DEBUG
            ????
            for(int?i=1;i<=p;++i){
            ????????
            if(!graph[i].adj.empty()){
            ????????????cout
            <<"node:"<<i<<"?";
            ???????????
            for(list<edge>::iterator?li?=?graph[i].adj.begin();
            ???????????????????li
            !=graph[i].adj.end();
            ???????????????????li
            ++){
            ???????????????cout
            <<"("<<li->node<<","<<li->weight<<")";
            ???????????}
            ???????????cout
            <<endl;
            ????????}
            ????}
            #endif

            ????
            for(int?i=1;i<=p;++i)
            ????????get_shortest(i);

            ????
            int?res?=?INT_MAX;

            ????
            for(int?i=1;i<=p;++i){
            ????????
            int?t?=?0;
            ????????
            for(int?j=0;j<n;++j){
            ????????????t
            +=?shortest_path[i][cow_place[j]];
            ????????}
            ????????res?
            =?min(res,t);
            ????}

            ????
            out<<res<<endl;

            }

            int?main(int?argc,char?*argv[])
            {
            ????solve();?
            ????
            return?0;
            }



            posted on 2009-07-06 20:05 YZY 閱讀(679) 評論(2)  編輯 收藏 引用 所屬分類: AlgorithmUSACO圖論

            評論

            # re: USACO 3.2 Sweet Butter[未登錄] 2009-08-17 00:10 intheway

            很欣賞你寫的代碼~  回復  更多評論   

            # re: USACO 3.2 Sweet Butter 2010-07-27 10:49 onlydyer

            .。是不是dijkstra寫錯了啊。。。我是說這個單詞  回復  更多評論   

            導航

            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            統計

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            亚洲中文字幕久久精品无码APP | 午夜福利91久久福利| 99久久成人国产精品免费| 久久av无码专区亚洲av桃花岛| 国产精品久久久久AV福利动漫| 狠狠色综合久久久久尤物| 亚洲精品NV久久久久久久久久 | 国产成人AV综合久久| 无码国内精品久久人妻麻豆按摩| 亚洲日本久久久午夜精品| 久久九九有精品国产23百花影院| 亚洲午夜久久久精品影院| 精品多毛少妇人妻AV免费久久| 精品午夜久久福利大片| 2019久久久高清456| 亚洲国产精品久久久久婷婷老年| 久久狠狠爱亚洲综合影院| 久久婷婷国产麻豆91天堂| 亚洲AV成人无码久久精品老人| 国产精品热久久毛片| 99国产欧美久久久精品蜜芽 | 久久久久久午夜精品| 午夜久久久久久禁播电影| 女同久久| 久久久久久青草大香综合精品 | 国产精品美女久久久久AV福利 | 国产精品久久久久久福利漫画| 国产免费久久精品99re丫y| 天天综合久久一二三区| 国产精品欧美久久久久天天影视 | 色综合久久天天综线观看| 99久久精品免费看国产一区二区三区 | 久久精品卫校国产小美女| 亚洲午夜精品久久久久久浪潮| 久久国产美女免费观看精品 | 久久99精品国产99久久| 国产精品久久久久aaaa| 97久久精品人人澡人人爽| 久久久WWW成人| 亚洲&#228;v永久无码精品天堂久久 | 91精品婷婷国产综合久久|