Re: [閒聊] 每日leetcode

[Wardyal (Wardyal)]

※ 引述《oin1104 (是oin的說)》之銘言：
: 引述《enmeitiryous (enmeitiryous)》
: 題目:
: 1514. Path with Maximum Probability

====

        double table[n][n];

        //init
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++){
                table[i][j] = 0;
            }
        }

        //get map
        for(int i = 0 ; i < edges.size() ; i++){
            table[edges[i][0]][edges[i][1]] = succProb[i];
            table[edges[i][1]][edges[i][0]] = succProb[i];
        }



====

昨天下班前看了一下這題 寫一半

今天繼續寫

結果我發現後面的測資有5000筆邊的資料

所以不能夠直接宣告一個

0.000000 0.500000 0.200000
0.500000 0.000000 0.500000
0.200000 0.500000 0.000000

類似這種的map

會Run Time Error = =

所以是要用Priority Queue嗎

我要去看解答了



--
環醬可愛
https://imgur.com/EF5SmX4.gif

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.91.73 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724899748.A.144.html
推 sustainer123: 瓦屌 這題考Dijkstra
→ sustainer123: 你要用Priority Queue
→ Wardyal: 我昨天看了一下Dijkstra 我看的那篇是先這樣宣告陣列的
推 enmeitiryous: 圖宣告的差異吧 改用adjacent list
→ enmeitiryous: 用adjacent matrix 時間需求到n**2
推 sustainer123: 這題n**2能過?
→ Wardyal: 不能過 我測過了 5000筆的測茲就爆了
推 enmeitiryous: leetcode 感覺抓上限過10**7可能就會爆了
推 sustainer123: 我印象>10**4就要nlogn才能過