Leetcode - Network Delay Time

#1

Đề bài: https://leetcode.com/problems/network-delay-time/

Ý tưởng và triển khai như source code và comment bên dưới:

class Solution 
{
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) 
    {
        // chuyển đổi vector times thành dạng đồ thị cạnh kề
        // với mỗi đỉnh u, có 1 vector cạnh kề (v, weight_to_v)
        std::unordered_map<int, std::vector<std::pair<int, int>>> graph;
        for (const std::vector<int>& time : times)
        {
            graph[time[0] - 1].push_back( { time[1] - 1, time[2] } );
        }
        
        // build một mảng khoảng cách ngắn nhất để đi từ đỉnh k đến các đỉnh còn lại
        std::vector<int> res = ShortestDistanceAllVertices(graph, n, k - 1);

        // tìm khoảng cách dài nhất để signal phát ra từ k phải truyền đi
        // để đến được điểm xa nhất trên đồ thị
        int max_time = 0;
        for (const int& n : res)
        {
            cout << n << " ";
            max_time = std::max(max_time, n);
        }
        
        // max_time == INT_MAX nghĩa là vẫn còn đỉnh không thể truyền tín hiệu đến
        return max_time == INT_MAX ? -1 : max_time;
    }
private:

    // cài đặt thuật toán Dijsktra
    // trả về một mảng đường đi ngắn nhất từ đỉnh k đến các đỉnh còn lại
    std::vector<int> ShortestDistanceAllVertices(std::unordered_map<int, std::vector<std::pair<int, int>>>& G, int num_vertices, int from)
    {
        if (from < 0 || from >= num_vertices)
            return {};
        
        std::vector<int> dist(num_vertices, INT_MAX);
        dist[from] = 0;

        std::vector<bool> visited(num_vertices, false);

        for (int count = 0; count < num_vertices; count++)
        {
            int u = DijsktraNextVertex(num_vertices, dist, visited);
            visited[u] = true;

            for (std::pair<int, int> p : G[u])
            {
                int v = p.first;
                int w = p.second;
                if (!visited[v] && w && dist[u] != INT_MAX && dist[u] + w < dist[v])
                {
                    dist[v] = dist[u] + w;
                    cout << v << " " << dist[v] << endl;
                }
            }
        }

        return dist;
    }
    
    int DijsktraNextVertex(int num_vertices, const std::vector<int> &dist, const std::vector<bool> &visited)
    {
        int minDist = INT_MAX;
        int minIdx = -1;

        for (int u = 0; u < num_vertices; u++)
        {
            if (!visited[u] && dist[u] <= minDist)
            {
                minDist = dist[u];
                minIdx = u;
            }
        }

        return minIdx;
    }
};

Kết quả output sai ở testcase như bên dưới:

Your input

[[3,5,78],[2,1,1],[1,3,0],[4,3,59],[5,3,85],[5,2,22],[2,4,23],[1,4,43],[4,5,75],[5,1,15],[1,5,91],[4,1,16],[3,2,98],[3,4,22],[5,4,31],[1,2,0],[2,5,4],[4,2,51],[3,1,36],[2,3,59]]
5
5

Output

81

Expected

31

stdout

15 22 81 31 0

Kết quả mong đợi là 31 (tín hiệu truyền từ 5 đến đỉnh 4 là xa nhất) , nhưng stdout cho thấy đi từ đỉnh 5 đến đỉnh 3 lại tốn đến 81 đơn vị khoảng cách.
Mình có sai về ý tưởng không? Có chổ nào sai trong phần cài đăt thuật toán nhỉ? :sweat_smile:

#2

nếu bạn đã biết vấn đề ở đâu, thì sao bạn không viết thêm vào dòng cout để debug quá trình thay đổi của biến đó (không giống như mong đợi của bạn)

1 Like
#5

Fixed, 52/52 test cases passed (but time limit exceed)

class Solution 
{
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) 
    {
        std::unordered_map<int, std::vector<std::pair<int, int>>> graph;
        for (const std::vector<int>& time : times)
        {
            graph[time[0] - 1].push_back( { time[1] - 1, time[2] } );
        }
        
        // for (auto p : graph)
        // {
        //     for (auto pp : p.second)
        //     {
        //         cout << p.first << " " << pp.first << " " << pp.second << endl;
        //     }
        // }
        
        std::vector<int> dist(n, INT_MAX);
        dist[k - 1] = 0;
        
        std::vector<bool> visited(n, false);
        visited[k - 1] = true;
        
        DFS(graph, dist, visited, n, k - 1);
        
//         std::queue<int> Q;
//         Q.push(k - 1);
//         dist[k - 1] = 0;
        
//         while (!Q.empty())
//         {
//             int u = Q.front();
//             Q.pop();
            
//             visited[u] = true;
            
//             for (int i = 0; i < graph[u].size(); i++)
//             {
//                 int v = graph[u][i].first;
//                 int w = graph[u][i].second;
                
//                 if (!visited[v])
//                     Q.push(v);
                
//                 if (dist[u] != INT_MAX && dist[u] + w < dist[v])
//                 {
//                     dist[v] = dist[u] + w;
//                 }
//             }
//         }
        
        int max_time = 0;
        for (const int& n : dist)
        {
            //cout << n << " ";
            max_time = std::max(max_time, n);
        }
        //cout << endl;
        
        return max_time == INT_MAX ? -1 : max_time;
    }
private:
    void DFS(std::unordered_map<int, std::vector<std::pair<int, int>>>& G, std::vector<int>& dist, std::vector<bool>& visited, int num, int cur)
    {
        if (cur < 0 || cur >= num)
            return;
        
        for (int i = 0; i < G[cur].size(); i++)
        {
            int next = G[cur][i].first;
            int weight = G[cur][i].second;
            
            if (!visited[next])
            {
                visited[next] = true;
                dist[next] = dist[cur] + weight;
                DFS(G, dist, visited, num, next);
            }
            else if (dist[cur] != INT_MAX && dist[cur] + weight < dist[next])
            {
                dist[next] = dist[cur] + weight;
                DFS(G, dist, visited, num, next);
            }
        }
    }
};
1 Like
#6

Fixed, 52/52 test cases passed sử dụng BFS.

class Solution 
{
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) 
    {
        std::unordered_map<int, std::vector<std::pair<int, int>>> graph;
        for (const std::vector<int>& time : times)
        {
            graph[time[0] - 1].push_back( { time[1] - 1, time[2] } );
        }
        
        std::vector<int> dist(n, INT_MAX);
        dist[k - 1] = 0;
        
        std::vector<bool> visited(n, false);
        visited[k - 1] = true;
        
        std::queue<int> Q;
        Q.push(k - 1);
        
        while (!Q.empty())
        {
            int u = Q.front();
            Q.pop();
            
            visited[u] = true;
            
            for (int i = 0; i < graph[u].size(); i++)
            {
                int v = graph[u][i].first;
                int w = graph[u][i].second;
                
                if (dist[u] != INT_MAX && dist[u] + w < dist[v])
                {
                    dist[v] = dist[u] + w;
                    Q.push(v);
                }
                else if (!visited[v])
                    Q.push(v);
            }
        }
        
        // DFS(graph, dist, visited, n, k - 1);
        
        int max_time = 0;
        for (const int& n : dist)
        {
            cout << n << " ";
            max_time = std::max(max_time, n);
        }
        cout << endl;
        
        return max_time == INT_MAX ? -1 : max_time;
    }
private:
//     void DFS(std::unordered_map<int, std::vector<std::pair<int, int>>>& G, std::vector<int>& dist, std::vector<bool>& visited, int num, int cur)
//     {
//         if (cur < 0 || cur >= num)
//             return;
        
//         for (int i = 0; i < G[cur].size(); i++)
//         {
//             int next = G[cur][i].first;
//             int weight = G[cur][i].second;
            
//             if (!visited[next])
//             {
//                 visited[next] = true;
//                 dist[next] = dist[cur] + weight;
//                 DFS(G, dist, visited, num, next);
//             }
//             else if (dist[cur] != INT_MAX && dist[cur] + weight < dist[next])
//             {
//                 cout << cur << " " << next << " " << dist[next] << endl;
//                 dist[next] = dist[cur] + weight;
//                 cout << cur << " " << next << " " << dist[next] << endl;
//                 DFS(G, dist, visited, num, next);
//             }
//         }
//     }
};
3 Likes
#7
#8
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?