• <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>

            Uriel's Corner

            Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
            posts - 0, comments - 50, trackbacks - 0, articles - 594

            POJ 3613 Cow Relays---Floyd+矩陣相乘

            Posted on 2011-05-02 17:39 Uriel 閱讀(776) 評論(0)  編輯 收藏 引用 所屬分類: POJ圖論

            這是在DY大牛第六期專題里列出的題目之一.

            話說搞ACM也2年多了, 竟然用矩陣乘法+Floyd的題目都還沒有做過... 上周的組隊(duì)賽遇到一道題才聽說... (沒有拜讀matrix67的神文... 檢討下... )

            /*
            POJ 3613 Cow Relays

            -------Classify: Floyd+矩陣乘法
            ----Description: 求從S到T恰好經(jīng)過K條邊(可重復(fù)走)的最短路
            -----------------K<=1e6, m<100(邊數(shù))
            ---Sample Input:

            2 6 6 4----------//K m s t
            11 4 6-----------//length x<->y
            4 4 8
            8 4 9
            6 6 8
            2 6 9
            3 8 9

            --Sample Output:

            10

            -----Time Limit: 1000Ms
            ---------Source: USACO 2007 November Gold
            -------Solution: 

                By Solution Report

                01鄰接矩陣A的K次方C=A^K,C[i][j]表示i點(diǎn)到j(luò)點(diǎn)正好經(jīng)過K條邊的路徑數(shù)

                      對應(yīng)于這道題,對鄰接圖進(jìn)行K次floyd之后,C[i][j]就是點(diǎn)i到j(luò)正好經(jīng)過K條邊的最短路


            ---------Status: AC C++ 532Ms
            -----------Date: 2011.05.02
            ------Reference: 
            http://hi.baidu.com/aconly/blog/item/23fb73acc1d874004b36d634.html
            -----------Code: 
            */


            #include
            <stdio.h>
            #include
            <stdlib.h>
            #include
            <string.h>
            #define N 1010
            #define INF 0x3f3f3f3f
            typedef 
            int M[N][N];

            int k, m, s, t, v;
            int ans[N][N], adj[N][N], vis[N], vtx[N], dis[N][N], tp[N][N];

            void floyd(M c, M a, M b) {
                
            int i, j, k;
                
            for (k = 0; k < v; ++k)
                    
            for (i = 0; i < v; ++i)
                        
            for (j = 0; j < v; ++j)
                            
            if (c[vtx[i]][vtx[j]] > a[vtx[i]][vtx[k]] + b[vtx[k]][vtx[j]])
                                c[vtx[i]][vtx[j]] 
            = a[vtx[i]][vtx[k]] + b[vtx[k]][vtx[j]];
            }


            void copy(M a, M b) {
                
            int i, j;
                
            for (i = 0; i < v; ++i)
                    
            for (j = 0; j < v; ++j) {
                        a[vtx[i]][vtx[j]] 
            = b[vtx[i]][vtx[j]];
                        b[vtx[i]][vtx[j]] 
            = INF;
                    }

            }


            void BS(int k) {
                
            while (k) {
                    
            if (k & 1{
                        floyd(dis, ans, adj);
                        copy(ans, dis);
                    }

                    floyd(tp, adj, adj);
                    copy(adj, tp);
                    k 
            >>= 1;
                }

            }


            int main() {
                
            int i, j, x, y, w;
                scanf(
            "%d %d %d %d"&k, &m, &s, &t);
                
            for (i = 0; i <= 1001++i) {
                    
            for (j = 0; j <= 1001++j) {
                        adj[i][j] 
            = INF;
                        tp[i][j] 
            = INF;
                        dis[i][j] 
            = INF;
                        ans[i][j] 
            = INF;
                    }

                    ans[i][i] 
            = 0;
                }

                v 
            = 0;
                memset(vis, 
            0sizeof(vis));
                
            for (i = 0; i < m; ++i) {
                    scanf(
            "%d %d %d"&w, &x, &y);
                    
            if (!vis[x]) {
                        vis[x] 
            = 1;
                        vtx[v
            ++= x;
                    }

                    
            if (!vis[y]) {
                        vis[y] 
            = 1;
                        vtx[v
            ++= y;
                    }

                    
            if (adj[x][y] > w)
                        adj[x][y] 
            = adj[y][x] = w;
                }

                BS(k);
                printf(
            "%d\n", ans[s][t]);
                
            return 0;
            }
            久久66热人妻偷产精品9| 看全色黄大色大片免费久久久| 久久精品中文字幕有码| A狠狠久久蜜臀婷色中文网| 久久天堂AV综合合色蜜桃网| 久久人人爽人人爽人人片av高请| 乱亲女H秽乱长久久久| 久久精品亚洲一区二区三区浴池| 日本久久久久亚洲中字幕| 精品国产91久久久久久久| 久久国产乱子精品免费女| 国产成人久久精品麻豆一区 | 久久精品国产免费观看三人同眠| 中文精品99久久国产| 久久这里只有精品18| 久久九九精品99国产精品| 老司机国内精品久久久久| 一本久久久久久久| 日本加勒比久久精品| 亚洲va久久久噜噜噜久久男同| 亚洲欧美伊人久久综合一区二区| 久久国产亚洲精品无码| 99精品久久久久久久婷婷| 欧美午夜A∨大片久久| 狠狠色婷婷久久一区二区| 国产一区二区三区久久| 亚洲国产成人精品无码久久久久久综合| 无码八A片人妻少妇久久| 国产成人无码久久久精品一| 久久久久久国产精品免费免费| 久久精品国产日本波多野结衣| 亚洲国产成人久久精品影视| 久久综合色老色| 91精品观看91久久久久久| 亚洲乱码精品久久久久..| 久久93精品国产91久久综合| 婷婷综合久久中文字幕蜜桃三电影| 国产成人无码精品久久久免费| 人人狠狠综合久久88成人| 久久久免费观成人影院| 成人久久久观看免费毛片|