前言

用的不熟练千万别用。

前置芝士：链式前向星

这玩意是个啥呢？先别着急，先上代码，再慢慢讲。

int head[MAXN];

struct Node{//定义
    long long to/*终点*/,dis/*权值*/,next/*上一个next的下标*/;
}edge[3000001];

void add(int t1/*起点*/,int t2/*终点*/,int t3/*变权*/) {//存入
    cnt++;
    edge[cnt].to=t2;
    edge[cnt].dis=t3;
    edge[cnt].next=head[t1];
    head[t1]=cnt;
}

链式前向星的定义和add的前三行应该都能看懂，但head数组和add的后两行可能有点懵，别急，先把链式前向星这几个字分开。

链式：很明显是链表，及对应add的后两行的操作，没看出来？稍等。

前向星：前，向，想到了没有，对应前一个操作（差不多也是链表），星呢？我个人认为是head数组。

明白了吧，再说一下add后两行，首先head数组，全体初始化为零，所以edge[cnt1].next=head[t1]=0,head[t1]=cnt1，但是，下一个以相同t1为起点的edge[cnt2].next呢？则为cnt1，懂了吧，单向链表。

如还有不清楚的地方可参考 there。

前置芝士2：BFS

自己百度。

正文

以下为堆优化写法。

好了可以开始我们的 dijkstra 了，作为最短路算法，dijkstra 一般分为这几步，首先存图，需要用到链式前向星，然后 BFS，最后出答案。

链式前向星介绍完了，出答案肯定不用说，BFS 一门也肯定百度了（shenxinbuyi），肯定就要说一下堆优化了。

别着急手打堆，有个现成的：优先队列，它采用堆优化，一般用pair或结构体加上重载运算符（我不会所以下面就不该这方面的代码了）辅助使用。

再来说一下堆，堆一般分为大根堆和小根堆，表示方法如下（优先队列）。

#define PII pair<int,int>
  
priority_queue<PII> q1;//小根堆
priority_queue<PII,vector<PII>,greater<PII> > q2;//大根堆

所以 BFS 加优先队列（堆）的代码就出来了，如下：

void dij() {
    for (register int i=1;i<=n;i++) {
        dis[i]=LLONG_MAX;//马上讲
    }
    dis[1]=0;
    q.push(make_pair(0,1));
    while (!q.empty()) {
        int x=q.top().second;
        q.pop();
        if (v[x]) {
            continue;
        }
        v[x]=1;//是否走过
        for (register int i=head[x];i;i=edge[i].next) {
            int y=edge[i].to;
            if (dis[y]>dis[x]+edge[i].dis) {
                dis[y]=dis[x]+edge[i].dis;
                q.push(make_pair(-dis[y],y));//小根堆
                //q.push(make_pair(dis[y],y));//大根堆
            }
        }
    }
}

可以发现大根堆和小根堆的操作别无二致，注意一下就行。

再来说一下dis数组，这个数组的意思是距离出发点的距离，而if (dis[y]>dis[x]+edge[i].dis)的操作则是判=是否为最短路，如果不是就dis[y]=dis[x]+edge[i].dis。

拿 B3602 举例，代码如下：

//不加注释了
#include <iostream>
#include <utility>
#include <queue>
#include <limits.h>

#define PII pair<long long ,long long>

using namespace std;
long long n,m,cnt;
priority_queue<PII> q;
long long  dis[3000001],v[3000001],head[3000001];

struct Node{
    long long to,dis,next;
}edge[3000001];

void add(int t1,int t2,int t3) {
    cnt++;
    edge[cnt].to=t2;
    edge[cnt].dis=t3;
    edge[cnt].next=head[t1];
    head[t1]=cnt;
}

void dij() {
    for (register int i=1;i<=n;i++) {
        dis[i]=LLONG_MAX;
    }
    dis[1]=0;
    q.push(make_pair(0,1));
    while (!q.empty()) {
        int x=q.top().second;
        q.pop();
        if (v[x]) {
            continue;
        }
        v[x]=1;
        for (register int i=head[x];i;i=edge[i].next) {
            int y=edge[i].to;
            if (dis[y]>dis[x]+edge[i].dis) {
                dis[y]=dis[x]+edge[i].dis;
                q.push(make_pair(-dis[y],y));
            }
        }
    }
}

int main() {
    cin>>n>>m;
    for (register int i=1;i<=m;i++) {
        int t1,t2,t3;
        cin>>t1>>t2>>t3;
        add(t1,t2,t3);
    }
    dij();
    for (register int i=1;i<=n;i++) {
        cout<<(dis[i]==LLONG_MAX?-1:dis[i])<<" ";
    }
    return 0;
}

\(finally\)

为什么说用的不熟别用呢，那是因为在打的时候，经常写错数组名，大小根堆写反，add写错等等。

友链：如还有不懂进。