• <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;
            }
            青青热久久综合网伊人| 亚洲国产精品一区二区三区久久| 久久久久亚洲AV成人片| 久久精品男人影院| 久久这里有精品视频| 亚洲国产精品无码久久久蜜芽| 久久91综合国产91久久精品| 久久涩综合| 国产精品久久久久…| 色综合久久88色综合天天 | 久久久久亚洲AV片无码下载蜜桃| 久久精品国产亚洲AV嫖农村妇女| 狠狠久久综合伊人不卡| 2021国产精品午夜久久| www亚洲欲色成人久久精品| 偷窥少妇久久久久久久久| 66精品综合久久久久久久| 久久久亚洲AV波多野结衣| 精品无码久久久久久国产| 久久夜色精品国产噜噜麻豆| 欧美亚洲日本久久精品| 色综合久久综合网观看| 欧洲成人午夜精品无码区久久 | a级毛片无码兔费真人久久| 久久久久久国产精品无码下载| 亚洲乱亚洲乱淫久久| 久久久久久国产精品免费无码| 久久亚洲精品无码aⅴ大香| 久久国产精品无码网站| 国产福利电影一区二区三区久久久久成人精品综合 | 亚洲国产精品一区二区三区久久| 久久r热这里有精品视频| 欧洲精品久久久av无码电影| 国产精品久久久久久久久久影院| 久久精品国产精品亚洲艾草网美妙| 久久久久女人精品毛片| 99久久国产宗和精品1上映| 欧美激情一区二区久久久| 婷婷久久综合九色综合绿巨人| 国产精品青草久久久久福利99 | 久久久免费精品re6|