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

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 閱讀(692) 評論(2)  編輯 收藏 引用 所屬分類: AlgorithmUSACO 、圖論

評論

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

很欣賞你寫的代碼~  回復(fù)  更多評論   

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

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

導(dǎo)航

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

統(tǒng)計

常用鏈接

留言簿(2)

隨筆分類

隨筆檔案

搜索

積分與排名

最新評論

閱讀排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            a91a精品视频在线观看| 亚洲第一在线综合网站| 亚洲欧美日韩一区二区| 一本大道久久精品懂色aⅴ| 欧美精品一区在线播放| 亚洲视频狠狠| 亚洲一区二区动漫| 国模精品一区二区三区| 欧美成人伊人久久综合网| 欧美成人激情视频免费观看| 日韩午夜激情电影| 在线综合视频| 国内精品一区二区三区| 欧美不卡视频| 国产精品高潮呻吟| 免费亚洲电影| 欧美午夜不卡影院在线观看完整版免费| 亚洲影院污污.| 欧美在线一二三| 99re国产精品| 欧美一区二区三区精品| 亚洲人成人一区二区三区| 一本久道久久综合狠狠爱| 国产真实乱偷精品视频免| 亚洲破处大片| 国模精品一区二区三区| 亚洲经典一区| 好看的日韩视频| 一区二区高清在线观看| 原创国产精品91| 中日韩美女免费视频网址在线观看 | 美女视频黄 久久| 欧美日本在线看| 久久久久女教师免费一区| 欧美日本国产| 欧美xx69| 国产一区二区三区精品久久久| 亚洲国产欧美一区二区三区同亚洲| 国产精品成人免费视频| 欧美激情视频一区二区三区免费 | 亚洲在线视频免费观看| 玖玖视频精品| 久久久亚洲欧洲日产国码αv | 欧美r片在线| 久久婷婷影院| 国产午夜一区二区三区| 夜夜爽99久久国产综合精品女不卡| 伊人一区二区三区久久精品| 亚洲一区欧美激情| 亚洲天堂久久| 欧美日韩综合视频网址| 亚洲国产精品一区二区www| 国内视频精品| 欧美一区二区在线观看| 午夜久久久久久| 国产精品激情av在线播放| 91久久视频| 亚洲精品日韩欧美| 欧美电影在线| 亚洲福利免费| 亚洲乱码国产乱码精品精可以看| 久久久伊人欧美| 欧美成人国产va精品日本一级| 国产亚洲精品久久久久动| 西瓜成人精品人成网站| 久久riav二区三区| 国产午夜一区二区三区| 欧美一二三视频| 久久先锋资源| 亚洲电影免费| 欧美精品999| 99成人在线| 欧美一区二区三区男人的天堂| 国产精品久久久久久久久借妻| 亚洲视频电影图片偷拍一区| 亚洲一区综合| 国产亚洲精品久久久久婷婷瑜伽| 欧美一区二区三区久久精品| 久久午夜视频| 亚洲精品资源| 国产精品第一区| 欧美一区三区二区在线观看| 久久综合给合| 亚洲蜜桃精久久久久久久| 欧美日韩免费观看中文| 亚洲图片欧洲图片av| 久久久久久自在自线| 亚洲第一免费播放区| 欧美日韩国产高清| 午夜精品久久久久久久久| 久久婷婷蜜乳一本欲蜜臀| 91久久精品日日躁夜夜躁国产| 欧美日韩高清在线| 午夜在线电影亚洲一区| 欧美成人久久| 亚洲综合色自拍一区| 国内在线观看一区二区三区| 欧美顶级少妇做爰| 午夜精品久久久久久久蜜桃app| 久久婷婷综合激情| 中文日韩在线| 在线观看成人一级片| 欧美精品v国产精品v日韩精品| 亚洲男女自偷自拍图片另类| 欧美大片一区二区| 午夜精品久久久久久久蜜桃app| 在线高清一区| 国产精自产拍久久久久久| 蜜臀99久久精品久久久久久软件| 亚洲特级片在线| 欧美高清成人| 久久精品在线观看| 亚洲无线一线二线三线区别av| 在线观看日韩| 国产精品推荐精品| 欧美精品一区二区三区四区| 欧美在线观看视频一区二区三区| 日韩视频不卡中文| 欧美大片免费| 久久精品一区二区三区中文字幕| 一区二区三区高清| 亚洲日本中文字幕区| 海角社区69精品视频| 国产精品成人国产乱一区| 欧美成人69av| 久久综合色影院| 久久福利一区| 亚洲自拍16p| 亚洲一级在线观看| 一本色道久久综合狠狠躁篇的优点 | 久久久亚洲午夜电影| 香蕉视频成人在线观看 | 91久久夜色精品国产九色| 久久综合九色综合欧美就去吻 | 在线欧美电影| 影音先锋欧美精品| 激情丁香综合| 精品成人在线| 亚洲高清免费| 亚洲欧洲综合另类| 亚洲精品美女| 99精品国产热久久91蜜凸| 亚洲另类自拍| 一区二区三区久久| 亚洲午夜国产成人av电影男同| 亚洲午夜影视影院在线观看| aaa亚洲精品一二三区| 99视频在线精品国自产拍免费观看| 亚洲精品少妇网址| 一区二区三区日韩| 中文在线一区| 欧美在线网址| 久久免费精品视频| 欧美成人官网二区| 亚洲精品日韩在线观看| 亚洲人成久久| 亚洲无线观看| 久久高清免费观看| 免费不卡在线观看| 欧美精品一区在线发布| 国产精品久久久久一区二区| 国产精品久久毛片a| 国产午夜精品久久久久久免费视 | 国产一区二区三区av电影 | 韩日视频一区| 亚洲精品免费电影| 亚洲欧美三级在线| 久久久国产午夜精品| 免费观看日韩av| 99在线精品观看| 久久岛国电影| 欧美精品福利| 韩国一区二区三区在线观看| 亚洲精选一区| 久久精品天堂| 亚洲精品欧美日韩专区| 国产一区二区三区精品久久久| 亚洲娇小video精品| 亚洲午夜视频在线| 久久久亚洲国产天美传媒修理工 | 免费在线国产精品| 夜夜嗨av一区二区三区四季av | 亚洲视频免费在线观看| 久久狠狠亚洲综合| 欧美视频你懂的| 亚洲电影免费在线观看| 亚洲欧美一区二区三区极速播放| 久久久久在线观看| av成人天堂| 欧美大片免费观看在线观看网站推荐 | 亚洲精品婷婷| 久久久精彩视频| 国产精品海角社区在线观看| 亚洲第一成人在线| 性欧美videos另类喷潮| 亚洲美女在线国产| 毛片基地黄久久久久久天堂| 欧美大片在线观看一区| 亚洲视频一区二区在线观看| 浪潮色综合久久天堂|