• <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年6月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            統計

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            久久久久噜噜噜亚洲熟女综合| 久久午夜无码鲁丝片午夜精品| 午夜精品久久影院蜜桃 | 久久综合成人网| 久久免费视频1| 久久99精品久久久久久动态图| 国内精品久久九九国产精品| 66精品综合久久久久久久| 久久久黄片| 少妇高潮惨叫久久久久久| 麻豆精品久久精品色综合| 精品久久人人做人人爽综合 | 综合久久一区二区三区 | 久久有码中文字幕| 欧美一区二区三区久久综| 97精品伊人久久大香线蕉| 欧美综合天天夜夜久久| 香蕉久久永久视频| 久久精品国产亚洲网站| 东方aⅴ免费观看久久av| 久久综合伊人77777| 国产亚洲精久久久久久无码| 久久婷婷是五月综合色狠狠| 69久久夜色精品国产69| 久久综合给久久狠狠97色| 久久久久国产日韩精品网站 | 国产精品一区二区久久精品无码| 国产精品福利一区二区久久| 国产精品久久久久久久人人看| 91精品观看91久久久久久| 久久精品aⅴ无码中文字字幕重口| 亚洲人成伊人成综合网久久久 | 久久精品无码专区免费青青 | 久久国产精品视频| 精品久久一区二区| 国产精品久久永久免费| 久久99国产精品一区二区| 久久A级毛片免费观看| 日韩久久久久久中文人妻| 亚洲精品乱码久久久久久久久久久久| 伊人久久亚洲综合影院|