• <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年8月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            統計

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            午夜欧美精品久久久久久久| 国产99久久久国产精品~~牛| 久久综合色区| 免费精品久久天干天干| 久久久久久国产精品美女 | 久久99国内精品自在现线| 国产产无码乱码精品久久鸭| 色成年激情久久综合| 久久精品国产亚洲av瑜伽| 亚洲中文字幕久久精品无码APP| 国产亚洲综合久久系列| 精品久久人人爽天天玩人人妻| 日韩va亚洲va欧美va久久| 亚洲级αV无码毛片久久精品 | 亚洲国产成人久久一区WWW| 中文字幕无码精品亚洲资源网久久| 国产午夜精品久久久久免费视 | 欧美黑人激情性久久| 996久久国产精品线观看| 亚洲国产精品无码久久青草 | 国产精品成人久久久| 国内精品久久国产大陆| 精品综合久久久久久98| 久久国产综合精品五月天| 大伊人青草狠狠久久| 成人久久免费网站| 国产视频久久| www.久久99| 99久久精品国产麻豆| 久久成人国产精品免费软件| 亚洲成av人片不卡无码久久| 国产精品欧美亚洲韩国日本久久 | 亚洲日韩欧美一区久久久久我| 精品熟女少妇a∨免费久久| 久久久久久免费视频| 欧美一级久久久久久久大片| 中文精品久久久久国产网址| 香蕉久久一区二区不卡无毒影院| 久久精品九九亚洲精品| 久久婷婷五月综合97色一本一本| 久久久久久综合网天天|