AcWing 1129. 热浪【单源最短路】

题目传送门

分析
单源点，正权图，求到终点的 最短路径

经典的 单源最短路 裸题，点数的范围是 \(n=2500\)，边数的范围是 \(m=12400\)

\(Dijkstra\) 朴素版 的 时间复杂度 为 \(O(n^2)\)，本题运算上界是 \(6.26×10^6\)
\(Dijkstra\) 堆优化版 的 时间复杂度 为 \(O(mlog_n)\)，本题运算上界是 \(1.36×10^5\)

任意选择其中之一都可

（还有，关于spfa他死了）

一、SPFA

#include 

using namespace std;
/*
(spfa) O(m)
平均O(m)，最坏O(nm) 一般会被卡到O(n*m)会被卡死
*/
const int N = 2510;               //端点数量
const int M = 6200 * 2 + 10;      //边的数量，记得别开太小，和N一样就等着挂吧
int n;                            // n个城镇
int m;                            // m条路径
int S;                            //起点
int T;                            //终点
int h[N], e[M], w[M], ne[M], idx; //邻接表
int dist[N];                      //最短距离数组
queue q;                     //队列
bool st[N];                       //是否使用过

//邻接表模板,建图,记得 memset(h,-1 ,sizeof h);
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

// spfa模板
void spfa() {
    //将所有距离初始化为无穷大
    memset(dist, 0x3f, sizeof dist);
    //出发点的距离清零
    dist[S] = 0;

    q.push(S);    //出发点入队列
    st[S] = true; //出发点标识已使用

    while (q.size()) {
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
}
int main() {
    //输入n个城镇，m条路径,S:起点，T:终点
    cin >> n >> m >> S >> T;
    //初始化邻接表
    memset(h, -1, sizeof h);
    //读入m条路径
    for (int i = 0; i < m; i++) {
        //每条路径的起点，终点，花费
        int a, b, c;
        cin >> a >> b >> c;
        //无向边
        add(a, b, c), add(b, a, c);
    }
    spfa();
    //输出终点T的单源最短距离
    cout << dist[T] << endl;

    return 0;
}

二、朴素版Dijkstra

#include 

using namespace std;
/*
(朴素dijkstra) O(n2)
 */

const int N = 2510;
const int M = 6200 * 2 + 10;

int n; // n个城镇
int m; // m条路径
int S; //起点
int T; //终点
//邻接表
int h[N], w[M], e[M], ne[M], idx;
bool st[N];  //是否使用过
int dist[N]; //最短距离数组

//维护邻接表
void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int dijkstra() {
    memset(dist, 0x3f, sizeof dist); //初始化为无穷大
    dist[S] = 0;                     //出发点的距离初始化为0

    for (int i = 0; i < n; i++) {
        //找到距离出发点最近的点
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;

        st[t] = true;
        for (int j = h[t]; ~j; j = ne[j]) {
            int k = e[j];
            dist[k] = min(dist[k], dist[t] + w[j]);
        }
    }
    return dist[T];
}

int main() {
    cin >> n >> m >> S >> T;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    cout << dijkstra() << endl;
    return 0;
}

三、堆优化版本Dijkstra

#include 
using namespace std;
/*
(堆优化dijkstra) O((n+m)logm)
时间复杂度查了好久，说什么的也有，保险起见，这里就采用那个最高的吧！
 */
const int N = 2510;
const int M = 6200 * 2 + 10;

typedef pair PII;
//邻接表
int h[N], w[M], e[M], ne[M], idx;
bool st[N];  //是否使用过
int dist[N]; //最短距离数组
//小顶堆
priority_queue, greater> heap;
int n; // n个城镇
int m; // m条路径
int S; //起点
int T; //终点

//维护邻接表
void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int dijkstra() {
    memset(dist, 0x3f, sizeof dist); //初始化为无穷大
    dist[S] = 0;                     //出发点的距离初始化为0
    heap.push({0, S});               //源点入队列
    // heap里装的 first:距离出发点的距离 second:结点编号
    while (heap.size()) {
        PII t = heap.top();
        heap.pop();
        //如果此结点已经被尝试过后，而且排在小顶堆的后面被尝试，说明不会更优秀
        if (st[t.second]) continue;
        //用这个点去尝试更新相关的点
        st[t.second] = true;
        for (int i = h[t.second]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > t.first + w[i]) {
                dist[j] = t.first + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    return dist[T];
}

int main() {
    cin >> n >> m >> S >> T;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    cout << dijkstra() << endl;
    return 0;
}