题目描述

模板代码，不懂留言

const int N = 110, M = 6010, INF = 0x3f3f3f3f;

typedef pair<int, int> PII;
#define x first
#define y second

int h[N], e[M], w[M], ne[M], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

class Solution {
public:
    void add(int a, int b, int c) {
        e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    }

    // 求1号点到n号点的最短距离
    void spfa(int start) 
    {
        memset(dist, 0x3f, sizeof dist);
        memset(st, false, sizeof st);
        queue<int> q;

        q.push(start);
        dist[start] = 0;

        while (q.size()) 
        {
            int t = q.front();
            q.pop();

            st[t] = false;
            for (int i = h[t]; i != -1; i = ne[i]) 
            {
                int j = e[i];

                if (dist[j] > dist[t] + w[i]) 
                {
                    dist[j] = dist[t] + w[i];
                    if (!st[j]) 
                    {
                        q.push(j);
                        st[j] = true;
                    }
                }
            }
        }
    }

    // 求1号点到n号点的最短距离
    void dijkstra(int start)
    {
        memset(dist, 0x3f, sizeof dist);
        memset(st, false, sizeof st);
        priority_queue<PII, vector<PII>, greater<PII>> heap;

        dist[start] = 0;
        heap.push({0, start});      // x存储距离，y存储节点编号

        while (heap.size())
        {
            auto t = heap.top();
            heap.pop();

            int ver = t.y, distance = t.x;

            if (st[ver]) continue;
            st[ver] = true;

            for (int i = h[ver]; i != -1; i = ne[i])
            {
                int j = e[i];

                if (dist[j] > distance + w[i])
                {
                    dist[j] = distance + w[i];
                    heap.push({dist[j], j});
                }
            }
        }
    }

    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        memset(h, -1, sizeof h);
        idx = 0;
        for (auto& e: times) 
        {
            int a = e[0], b = e[1], c = e[2];
            add(a, b, c);
        }

        dijkstra(k);
        // spfa(k);

        int res = 1;
        for (int i = 1; i <= n; i ++ ) res = max(res, dist[i]);
        if (res == INF) res = -1;
        return res;
    }
};