• <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>
            隨筆 - 87  文章 - 279  trackbacks - 0
            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊(cè)

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217774
            • 排名 - 117

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            寫了個(gè)比較通用的堆,可直接用作優(yōu)先隊(duì)列

            Silver Cow Party
            Time Limit:2000MS  Memory Limit:65536K
            Total Submit:1112 Accepted:326

            Description

            One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X (1 ≤ XN). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires Ti (1 ≤ Ti ≤ 100) units of time to traverse.

            Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow's return route might be different from her original route to the party since roads are one-way.

            Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?

             

            Input
            Line 1: Three space-separated integers, respectively: N, M, and X
            Lines 2..M+1: Line i+1 describes road i with three space-separated integers: Ai, Bi, and Ti. The described road runs from farm Ai to farm Bi, requiring Ti time units to traverse.

            Output
            Line 1: One integer: the maximum of time any one cow must walk.

            Sample Input

            4 8 2
            1 2 4
            1 3 2
            1 4 7
            2 1 1
            2 3 5
            3 1 2
            3 4 4
            4 2 3

             

            Sample Output

            10

             

            Hint
            Cow 4 proceeds directly to the party (3 units) and returns via farms 1 and 3 (7 units), for a total of 10 time units.

            Source
            USACO 2007 February Silver



            #include <iostream>
            using namespace std;

            const int INF = 1 << 28;

            int adj[1001][1001], adjw[1001][1001], na[1001];
            int n, m, x;


            //heap sink,swim,getmin,insert參數(shù)均為外部編號(hào),wt為其權(quán)值
            int heap[100001], id[100001], hsize;
            int *key;
            void init(int s, int *wt) {
                
            int i;
                hsize 
            = s; 
                key 
            = wt;
                
            for (i=1; i<=hsize; i++{
                    heap[i] 
            = i;
                    id[i] 
            = i;
                }

            }

            void swim(int u) {
                
            int p = id[u], q = p >> 1, ku = key[u];
                
            while (q && ku < key[heap[q]]) {
                    id[heap[q]] 
            = p;
                    heap[p] 
            = heap[q];
                    p 
            = q;
                    q 
            = p >> 1;
                }

                id[u] 
            = p;
                heap[p] 
            = u;
            }

            void sink(int u) {
                
            int p = id[u],q = p << 1, ku = key[u];
                
            while (q <= hsize) {
                    
            if (q < hsize && key[heap[q+1]] < key[heap[q]]) q++;
                    
            if (key[heap[q]] >= ku) break;
                    id[heap[q]] 
            = p;
                    heap[p] 
            = heap[q];
                    p 
            = q; 
                    q 
            = p << 1;
                }

                id[u] 
            = p;
                heap[p] 
            = u;
            }

            int getmin() {
                
            int ret = heap[1];
                id[ret] 
            = -1;
                id[heap[hsize]] 
            = 1;
                heap[
            1= heap[hsize];
                hsize
            --;
                sink(heap[
            1]);
                
            return ret;
            }

            void insert(int u) {
                heap[
            ++hsize] = u;
                id[u] 
            = hsize;
                swim(u);
            }

            void build() {
                
            int i;
                
            for (i=hsize/2; i>0; i--) sink(heap[i]);
            }

            bool isEmpty() {
                
            return hsize == 0;
            }

            int dijkstraHeap(int beg, int end=-1{
                
            int i, j, k, u, v, w;
                
            int dist[1001], chk[1001];
                
            for (i=1; i<=n; i++{
                    dist[i] 
            = INF;
                    chk[i] 
            = 0;
                }

                init(n, dist);
                dist[beg] 
            = 0; swim(beg);
                
            while (!isEmpty()) {
                    u 
            = getmin();
                    
            if (u == end) break;
                    chk[u] 
            = 1;
                    
            for (i=0; i<na[u]; i++{
                        v 
            = adj[u][i];
                        w 
            = adjw[u][i];
                        
            if (dist[v] > dist[u] + w) {
                            dist[v] 
            = dist[u] + w;
                            swim(v);
                        }

                    }

                }

                
            if (end == -1return dist[n];
                
            return dist[end];
            }


            int main() {
                
            int i, j, k, u, v, w;
                
            int val[1001];
                scanf(
            "%d%d%d"&n, &m, &x);
                
            for (i=0; i<m; i++{
                    scanf(
            "%d%d%d"&u, &v, &w);
                    adj[u][na[u]] 
            = v; 
                    adjw[u][na[u]] 
            = w;
                    na[u]
            ++;
                }

               
                dijkstraHeap(x);
                memcpy(val, key, 
            sizeof(val));
                
                
            int ans = 0;
                
            for (i=1; i<=n; i++{
                    
            int tmp = dijkstraHeap(i,x);
                    
            if (tmp+val[i] > ans) ans = tmp + val[i];
                }

                
                printf(
            "%d\n", ans);
                
            return 0;
            }
            posted on 2007-07-23 20:51 閱讀(1289) 評(píng)論(4)  編輯 收藏 引用 所屬分類: 數(shù)據(jù)結(jié)構(gòu)與算法ACM題目

            FeedBack:
            # re: pku3268 dij+heap 2007-07-27 08:41 oyjpart
            終于更新blog了。。。  回復(fù)  更多評(píng)論
              
            # re: pku3268 dij+heap 2007-08-01 20:29 relic
            不必n次dijkstra,只要把所有邊反向,再來一次dijkstra就可以了。算上第一次一共兩次dij  回復(fù)  更多評(píng)論
              
            # re: pku3268 dij+heap 2007-08-03 22:58 
            偷懶了:)  回復(fù)  更多評(píng)論
              
            # re: pku3268 dij+heap 2007-09-18 13:16 drizzlecrj
            @relic
            re  回復(fù)  更多評(píng)論
              
            久久免费看黄a级毛片| 久久人爽人人爽人人片AV| 国产成人99久久亚洲综合精品| 青青热久久综合网伊人| 久久午夜福利电影| 久久久久亚洲av无码专区导航| 久久久国产精品福利免费| 日韩久久久久中文字幕人妻| 久久99精品久久久大学生| 爱做久久久久久| 亚洲国产另类久久久精品| 色综合久久88色综合天天| 久久婷婷五月综合色奶水99啪| 久久精品国产精品青草app| 久久天天躁夜夜躁狠狠躁2022| 久久精品国产亚洲精品2020| 久久婷婷五月综合成人D啪| 久久这里只有精品首页| 无码国产69精品久久久久网站| 久久久久这里只有精品| 久久综合丁香激情久久| 蜜臀av性久久久久蜜臀aⅴ麻豆 | 久久精品国产2020| 久久精品国产亚洲AV不卡| 久久精品国产亚洲av影院| 四虎国产精品成人免费久久| 中文字幕久久欲求不满| 91精品国产乱码久久久久久| 欧美精品九九99久久在观看| 久久99国产精品成人欧美| 国产精品国色综合久久| 色欲久久久天天天综合网精品| 久久亚洲AV成人无码软件 | 久久人妻无码中文字幕| 久久青青国产| 国产欧美久久久精品影院| 久久亚洲国产成人影院| 欧美精品国产综合久久| 综合网日日天干夜夜久久| 久久综合狠狠综合久久综合88| 伊人久久精品无码av一区|