• <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;
            }
            成人国内精品久久久久影院VR| 久久综合九色综合精品| 午夜福利91久久福利| 无码8090精品久久一区| 欧美亚洲国产精品久久高清| 久久久婷婷五月亚洲97号色| 亚洲一本综合久久| 一本色道久久99一综合| 久久―日本道色综合久久| 性高朝久久久久久久久久| 人妻精品久久久久中文字幕69| 久久99精品久久久久久水蜜桃| 精品久久亚洲中文无码| 久久福利片| 国产麻豆精品久久一二三| 伊人久久大香线蕉综合5g| 日韩精品国产自在久久现线拍| 中文无码久久精品| 日本加勒比久久精品| 久久免费线看线看| 久久永久免费人妻精品下载| 亚洲v国产v天堂a无码久久| 久久r热这里有精品视频| 日韩人妻无码精品久久免费一| 国产无套内射久久久国产| 久久精品国产亚洲77777| 久久久国产精华液| 久久国内免费视频| 亚洲国产成人精品女人久久久 | 九九久久精品国产| 久久精品国产69国产精品亚洲| 亚洲国产精品一区二区久久hs| 人妻无码αv中文字幕久久琪琪布 人妻无码精品久久亚瑟影视 | 无码国内精品久久人妻蜜桃| 欧美精品一区二区久久| 国产91久久综合| 久久精品一区二区| 国产精品日韩深夜福利久久| 91麻精品国产91久久久久| 99久久精品免费观看国产| 91久久精品国产91性色也|