• <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 閱讀(778) 評論(0)  編輯 收藏 引用 所屬分類: POJ圖論

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

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

            /*
            POJ 3613 Cow Relays

            -------Classify: Floyd+矩陣乘法
            ----Description: 求從S到T恰好經過K條邊(可重復走)的最短路
            -----------------K<=1e6, m<100(邊數)
            ---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點到j點正好經過K條邊的路徑數

                      對應于這道題,對鄰接圖進行K次floyd之后,C[i][j]就是點i到j正好經過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;
            }
            亚洲国产成人久久笫一页| 色欲久久久天天天综合网精品| 久久久久久久人妻无码中文字幕爆| 久久久一本精品99久久精品88| 久久综合狠狠综合久久| 老司机国内精品久久久久| 久久亚洲高清综合| av色综合久久天堂av色综合在| 色综合色天天久久婷婷基地| 中文成人无码精品久久久不卡 | 狠狠精品久久久无码中文字幕| 精品一久久香蕉国产线看播放 | 91精品国产91久久久久久| 久久精品国产精品亚洲| 伊人久久精品无码二区麻豆| 久久99国产精品二区不卡| 久久亚洲精品国产亚洲老地址| 国产国产成人精品久久| 久久综合视频网| 久久无码国产| 91麻精品国产91久久久久 | 亚洲精品乱码久久久久久自慰 | 久久99精品国产| 综合人妻久久一区二区精品| 中文字幕久久欲求不满| 91久久婷婷国产综合精品青草| 精品国产日韩久久亚洲| 老司机国内精品久久久久| 浪潮AV色综合久久天堂| 日韩欧美亚洲综合久久| 亚洲欧美日韩精品久久亚洲区 | 久久久久久久精品妇女99| 久久99热这里只有精品国产 | 中文字幕无码av激情不卡久久| 女人香蕉久久**毛片精品| 国产产无码乱码精品久久鸭| 久久无码人妻一区二区三区午夜| 人妻无码精品久久亚瑟影视| 综合久久一区二区三区| 久久久国产视频| 亚洲熟妇无码另类久久久|