LeetCode——743. 網絡延遲時間

網絡延遲時間

• 題目
• 思路
• 代碼
• 結果

題目

有 n 個網絡節點，标記為 1 到 n。

給你一個清單 times，表示信号經過 有向 邊的傳遞時間。 times[i] = (ui, vi, wi)，其中 ui 是源節點，vi 是目标節點， wi 是一個信号從源節點傳遞到目标節點的時間。

現在，從某個節點 K 發出一個信号。需要多久才能使所有節點都收到信号？如果不能使所有節點收到信号，傳回 -1 。

思路

其實我自己是沒有一個很完整且準确的思路的，這道題，看起來其實就是一個找到從某個節點出發的最短路徑的最大值！

看了題解，用弗洛伊德算法來解決！

因為最大不超過100個節點，可以用鄰接圖來存放兩個節點之間是否連通！

然後，就利用一個周遊算法，比如從a點到b點，直接距離和經過c點，即從a到c，再從c到b的距離。兩者比較取其小的數值！

然後，看要求，是為了取出從某個目标節點出發的，最大傳遞時間。是以要周遊一下k列的最大值！

代碼

class Solution {
    int N=110;  // 節點個數
    int map[][] = new  int[N][N];// 連通圖
    int INF=0x3f3f3f3f;
    public int networkDelayTime(int[][] times, int n, int k)
    {
        for (int i=1;i<=n;++i)
        {
            for (int j=1;j<=n;++j)
                map[i][j]=map[j][i]=((i==j)?0:INF);
        }
        // 給有向路徑指派
        for(int[] t:times)
        {
            int u=t[0],v=t[1],c=t[2];
            map[u][v]=c;
        }

    //第一層循環設定中間點i，第二層循環設定起始點j，第三層循環設定結束點g。
        for (int p=1;p<=n;++p)
        {
            for (int i=1;i<=n;++i)
            {
                for (int j=1;j<=n;++j)
                {
                    map[i][j]=Math.min(map[i][j],map[i][p]+map[p][j]);
                }
            }
        }

        int ans=0;
        for (int i=1;i<=n;++i)
            ans=Math.max(ans,map[k][i]);
        return ans>=INF/2?-1:ans;
    }
}
           

結果

弗洛伊德算法，雖然這是複雜度最高的，看來這幾天要把最短路徑再重新學一學，這種寫法很慢，不過這應該是從大二開始學了最短路徑算法後，第一次用到實際的地方！