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

oyjpArt ACM/ICPC算法程序設計空間

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

PKU1511 Invitation Cards

Posted on 2007-01-02 16:10 oyjpart 閱讀(1606) 評論(2)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽

Invitation Cards
Time Limit:3000MS? Memory Limit:65536K
Total Submit:241 Accepted:93

Description
In the age of television, not many people attend theater performances. Antique Comedians of Malidinesia are aware of this fact. They want to propagate theater and, most of all, Antique Comedies. They have printed invitation cards with all the necessary information and with the programme. A lot of students were hired to distribute these invitations among the people. Each student volunteer has assigned exactly one bus stop and he or she stays there the whole day and gives invitation to people travelling by bus. A special course was taken where students learned how to influence people and what is the difference between influencing and robbery.

The transport system is very special: all lines are unidirectional and connect exactly two stops. Buses leave the originating stop with passangers each half an hour. After reaching the destination stop they return empty to the originating stop, where they wait until the next full half an hour, e.g. X:00 or X:30, where 'X' denotes the hour. The fee for transport between two stops is given by special tables and is payable on the spot. The lines are planned in such a way, that each round trip (i.e. a journey starting and finishing at the same stop) passes through a Central Checkpoint Stop (CCS) where each passenger has to pass a thorough check including body scan.

All the ACM student members leave the CCS each morning. Each volunteer is to move to one predetermined stop to invite passengers. There are as many volunteers as stops. At the end of the day, all students travel back to CCS. You are to write a computer program that helps ACM to minimize the amount of money to pay every day for the transport of their employees.

Input
The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case begins with a line containing exactly two integers P and Q, 1 <= P,Q <= 1000000. P is the number of stops including CCS and Q the number of bus lines. Then there are Q lines, each describing one bus line. Each of the lines contains exactly three numbers - the originating stop, the destination stop and the price. The CCS is designated by number 1. Prices are positive integers the sum of which is smaller than 1000000000. You can also assume it is always possible to get from any stop to any other stop.

Output
For each case, print one line containing the minimum amount of money to be paid each day by ACM for the travel costs of its volunteers.

Sample Input

2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

Sample Output

46
210

Source
Central Europe 1998

這個題目我想就是專考Dijkstra()的堆寫法吧 中間我采用的逆轉有向邊的寫法 可以把從多點到單源的最短路徑用單源到多點的最短路徑的方法求出。
中間出了一個很隱蔽的錯誤 在一個i, j的雙層循環中 內層循環寫成了i++...結果調了很久。。。
總算過了 發現STL占內存是直接寫鄰接表的2倍左右,這也印證了vector的擴張方式。

??1 Solution:
??2 // by?Optimistic
??3 #include? < stdio.h >
??4 #include? < string .h >
??5 #include? < vector >
??6 using ? namespace ?std;?
??7
??8 const ? int ?MAXINT? = ? 200000000 ;
??9 // const?double?INF?=?10e100;
?10 // const?double?EPS?=?10e-6;?
?11
?12 const ? int ?N? = ? 1000010 ;
?13 int ?nv,?ne;
?14 typedef? struct { int ?jj,?w;} Vtx;
?15 vector < Vtx > ?adj[N];
?16 vector < Vtx > ?adj2[N];
?17 typedef? struct { int ?k,?no;} hNode;
?18 int ?ntc,?hs;
?19 hNode?h[N];?
?20
?21 bool ? operator ? < ?( const ?hNode & ?a,? const ?hNode & ?b)?
?22 {
?23 ? return ?a.k? < ?b.k;
?24 }
?
?25
?26 void ?push(hNode?t)
?27 {
?28 ? int ?i? = ? ++ hs;
?29 ? while (i? > ? 1 ? && ?t? < ?h[i >> 1 ])? {
?30 ??h[i]? = ?h[i >> 1 ];
?31 ??i? >>= ? 1 ;
?32 ?}

?33 ?h[i]? = ?t;
?34 }
?
?35
?36 void ?pop()
?37 {
?38 ?hs -- ;
?39 ? int ?i? = ? 1 ,?ic? = ? 2 ;
?40 ? while (ic? <= ?hs)? {
?41 ?? if (ic + 1 ? <= ?hs? && ?h[ic + 1 ]? < ?h[ic])?ic ++ ;
?42 ?? if (h[hs + 1 ]? < ?h[ic])? break ;
?43 ??h[i]? = ?h[ic];
?44 ??i? = ?ic;
?45 ??ic? <<= ? 1 ;
?46 ?}

?47 ?h[i]? = ?h[hs + 1 ];
?48 }
?
?49
?50 int ?Dijkstra()
?51 {
?52 ?hs? = ? 0 ;
?53 ? int ?i;
?54 ? int ? * ?dist? = ? new ? int [nv];
?55 ? for (i? = ? 0 ;?i? < ?nv;?i ++ )?dist[i]? = ?MAXINT;
?56 ?hNode?now;
?57 ?now.k? = ? 0 ;?now.no? = ? 0 ;
?58 ?push(now);
?59 ? while ( 1 )
?60 ? {
?61 ?? while (hs? > ? 0 ? && ?h[ 1 ].k? > ?dist[h[ 1 ].no])?
?62 ???pop();
?63 ?? if (hs? == ? 0 )? break ;
?64 ??now? = ?h[ 1 ];
?65 ??pop();
?66 ?? int ?u? = ?now.no;
?67 ??dist[u]? = ?now.k;
?68 ?? for (i? = ? 0 ;?i? < ?adj[u].size();?i ++ )
?69 ?? {
?70 ??? int ?v? = ?adj[u][i].jj;
?71 ??? int ?w? = ?adj[u][i].w;
?72 ??? if (dist[v]? > ?dist[u]? + ?w)
?73 ??? {
?74 ????now.k? = ?dist[u]? + ?w;
?75 ????now.no? = ?v;
?76 ????push(now);
?77 ????dist[v]? = ?dist[u]? + ?w;
?78 ???}

?79 ??}

?80 ?}

?81 ? int ?ans? = ? 0 ;
?82 ? for (i? = ? 0 ;?i? < ?nv;?i ++ )
?83 ??ans? += ?dist[i];
?84 ? return ?ans;
?85 }
?
?86
?87 void ?init()
?88 {
?89 ? int ?i,?u,?v,?w;
?90 ?Vtx?x;
?91 ? // initiation
?92 ? for (i? = ? 0 ;?i? < ?nv;?i ++ )? {
?93 ??adj2[i].clear();
?94 ??adj[i].clear();
?95 ?}

?96 ? // input
?97 ?scanf( " %d?%d " ,? & nv,? & ne);
?98 ? for (i? = ? 0 ;?i? < ?ne;?i ++ )? {
?99 ??scanf( " %d?%d?%d " ,? & u,? & v,? & w);
100 ??u -- ;?v -- ;?
101 ??x.jj? = ?v;?x.w? = ?w;
102 ??adj[u].push_back(x);
103 ?}

104 ? // pretreatment
105 }
?
106
107 void ?Reverse()
108 {
109 ? int ?i,?j;
110 ?Vtx?x;
111 ? for (i? = ? 0 ;?i? < ?nv;?i ++ )
112 ??adj2[i].clear();
113 ? for (i? = ? 0 ;?i? < ?nv;?i ++ )
114 ? {
115 ?? for (j? = ? 0 ;?j? < ?adj[i].size();?j ++ )
116 ?? {
117 ???x.jj? = ?i;
118 ???x.w? = ?adj[i][j].w;
119 ???adj2[adj[i][j].jj].push_back(x);
120 ??}

121 ?}

122 ? for (i? = ? 0 ;?i? < ?nv;?i ++ )
123 ? {
124 ??adj[i].clear();
125 ?? for (j? = ? 0 ;?j < adj2[i].size();?j ++ )
126 ???adj[i].push_back(adj2[i][j]);
127 ?}

128 }
?
129
130 void ?work()
131 {
132 ? int ?x? = ?Dijkstra();
133 ?Reverse();
134 ?x? += ?Dijkstra();
135 ?printf( " %d\n " ,?x);
136 }
?
137
138 int ?main()
139 {
140 // ?freopen("t.in",?"r",?stdin);
141 ?scanf( " %d " ,? & ntc);
142 ? while (ntc -- )
143 ? {
144 ??init();
145 ??work();
146 ?}

147 ? return ? 0 ;
148 }
?
149

Feedback

# re: PKU1511 Invitation Cards   回復  更多評論   

2007-04-16 22:38 by bon
while (hs > 0 && h[ 1 ].k > dist[h[ 1 ].no]) pop();
請問這一句是什么意思?多謝!

# re: PKU1511 Invitation Cards   回復  更多評論   

2007-04-17 13:02 by oyjpart
72 if (dist[v] > dist[u] + w)
73 {
74 now.k = dist[u] + w;
75 now.no = v;
76 push(now);
77 dist[v] = dist[u] + w;
78 }
從這段代碼中可以看到 在一次添加節點后 并沒有按照常理對其他連接的可改進節點做修正(實際上是模版沒有擴充修改一個節點的值然后維護堆性質的功能) 我們把那些舊的節點稱為廢節點的話 所以在選出dist最小的節點的時候要看看是不是廢節點 如果是的就要不斷POP出來
while (hs > 0 && h[ 1 ].k > dist[h[ 1 ].no]) pop();
應該很好理解了
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产日韩欧美不卡| 欧美四级在线观看| 伊人久久亚洲影院| 免费久久99精品国产自| 久热综合在线亚洲精品| 中文精品视频| 国产精品羞羞答答xxdd| 久久久久青草大香线综合精品| 午夜精品久久久久99热蜜桃导演| 国产亚洲欧美日韩日本| 嫩草伊人久久精品少妇av杨幂| 欧美成人综合网站| 午夜精品久久久久影视| 香蕉久久夜色精品国产使用方法| 黑人一区二区| 一级成人国产| 伊人久久大香线蕉综合热线| 亚洲黄色在线看| 国产精品久久7| 六月婷婷一区| 欧美视频免费在线| 免费亚洲电影| 国产精品狼人久久影院观看方式| 久久精品一二三区| 欧美激情国产日韩| 久久久国产成人精品| 欧美国产一区在线| 久久久久久久久久久一区| 欧美激情中文字幕乱码免费| 久久精品91| 欧美视频官网| 亚洲国产精品日韩| 国内精品视频一区| 亚洲手机在线| 99精品视频免费观看| 午夜在线a亚洲v天堂网2018| 99ri日韩精品视频| 狂野欧美激情性xxxx欧美| 久久www成人_看片免费不卡| 欧美精品激情blacked18| 麻豆精品传媒视频| 国产日韩欧美黄色| 国产精品99久久99久久久二8| 亚洲欧洲一二三| 久久久久欧美| 久久久亚洲一区| 国产精品一级二级三级| 99ri日韩精品视频| 9i看片成人免费高清| 欧美成人激情视频免费观看| 另类av导航| 在线观看精品| 久久乐国产精品| 久久久国产精品亚洲一区| 国产精品一卡二| 午夜国产不卡在线观看视频| 亚洲综合三区| 国产精品男女猛烈高潮激情| 一区二区三区精密机械公司| 在线亚洲一区二区| 欧美三级在线| 亚洲一区二区三区777| 亚洲永久网站| 国产精品久久午夜夜伦鲁鲁| 一区二区成人精品| 性高湖久久久久久久久| 国产精品一区视频| 欧美在线免费看| 久久综合综合久久综合| 亚洲成色777777在线观看影院 | 亚洲精选中文字幕| 欧美成人精品福利| 亚洲日本成人网| 亚洲午夜羞羞片| 国产欧美欧美| 久久人体大胆视频| 亚洲黄色影片| 香蕉视频成人在线观看| 国产在线观看一区| 蘑菇福利视频一区播放| 日韩性生活视频| 欧美一区二区在线播放| 一区二区在线观看av| 欧美成人四级电影| 中日韩男男gay无套| 久久精品日产第一区二区| 亚洲高清资源| 欧美人交a欧美精品| 亚洲欧美日韩在线不卡| 免费在线欧美视频| 国产精品99久久久久久白浆小说| 国产精品网站在线播放| 老司机一区二区| 亚洲视频在线观看网站| 麻豆精品一区二区综合av| 亚洲乱码国产乱码精品精天堂| 欧美午夜精品久久久久久超碰| 午夜精品久久久久久久久久久久| 美女被久久久| 亚洲性色视频| 在线欧美福利| 国产精品一区亚洲| 欧美黄色精品| 欧美一区二区在线免费播放| 亚洲国产精品一区二区www| 午夜一区二区三区在线观看| 亚洲第一主播视频| 国产欧美日韩视频| 欧美久久电影| 久久久久久久波多野高潮日日| 在线一区亚洲| 亚洲精美视频| 欧美成年人网| 久久精品欧美日韩精品| 亚洲视频免费| 亚洲精品乱码久久久久久久久| 国产视频亚洲| 国产精品户外野外| 欧美国产极速在线| 久久天堂国产精品| 欧美中在线观看| 亚洲视频日本| 日韩午夜精品视频| 亚洲福利视频专区| 美女主播精品视频一二三四| 香蕉国产精品偷在线观看不卡| 日韩一级黄色大片| 亚洲第一精品在线| 精品福利av| 一区在线视频| 伊人久久大香线蕉av超碰演员| 国产精品有限公司| 国产精品网站在线| 国产精品成人一区| 欧美午夜在线视频| 欧美视频一区二区三区| 欧美日韩国产欧| 欧美女人交a| 欧美日韩在线播放三区四区| 欧美精品99| 欧美理论片在线观看| 欧美成人午夜77777| 欧美劲爆第一页| 欧美精品成人一区二区在线观看 | 久久久中精品2020中文| 久久精品中文字幕一区| 久久精品国产精品亚洲综合| 久久国内精品自在自线400部| 久久国产精品99国产| 久久久久久尹人网香蕉| 欧美a级片一区| 欧美日韩免费在线| 国产精品久久久久影院色老大| 国产精品美女主播| 狠狠色香婷婷久久亚洲精品| 亚洲风情亚aⅴ在线发布| 亚洲精品久久久久中文字幕欢迎你| 99av国产精品欲麻豆| 亚洲欧美日韩综合| 久久人体大胆视频| 欧美激情综合色| 一区二区av在线| 久久aⅴ国产紧身牛仔裤| 免费不卡视频| 国产精品av免费在线观看| 国产精品人成在线观看免费| 国内精品伊人久久久久av一坑| 亚洲高清不卡在线观看| 国产精品99久久不卡二区| 欧美有码在线观看视频| 欧美大片一区二区| 夜夜精品视频一区二区| 欧美在线一二三| 欧美日韩国产成人精品| 国产视频丨精品|在线观看| 91久久精品国产91久久性色tv| 亚洲图片在线观看| 久久久久久免费| 亚洲精选一区| 久久精品国产96久久久香蕉| 欧美另类videos死尸| 国产亚洲福利| 99视频有精品| 美女露胸一区二区三区| 一区二区三区免费观看| 久久综合九色九九| 国产精品亚发布| 一本一道久久综合狠狠老精东影业 | 亚洲欧美日韩国产成人精品影院| 久久午夜国产精品| 99精品国产一区二区青青牛奶| 久久国产精品99国产| 欧美午夜一区二区三区免费大片| 亚洲第一免费播放区| 欧美一站二站| 一区二区毛片| 欧美黄色日本| 亚洲激情影视| 麻豆av福利av久久av| 性欧美videos另类喷潮|