链式前向星存储边

（全网唯一一个对每个变量意义进行明确说明的题解！！）

1. 用一个node结构体来存储每一条边的信息，int v,w,pre; 
   其中v是这条边的终点，ｗ是这条边的权重，而最重要的是pre，
   存的是与这一条边同一个起点的上一条边的序号

2. 另外还有一个p[n]的数组，其中p[i]来保存第i个点的最后一条
   边的序号。所以到时候遍历边的时候是倒序遍历。

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define MAX 10000000
int nEdge;//代表的是输入边的总数
int p[MAX];//p[i]保存的是连接第i个点的最后一条边的序号。

struct node
{
    int v,w,pre;//pre保存的是上一条边的序号（输入时的序号）
} e[MAX];

void addEdge(int u,int v,int w)//把u->v权重为w的边加入到边集。
{
    nEdge++;//新增了一条u->v的边，此时这条边的序号是nEdge；
    e[nEdge].v = v;
    e[nEdge].w = w;
    e[nEdge].pre = p[u];//连接u点这条边的上一条边的序号是p[u];
    p[u] = nEdge;//连接u点又新增了一条边，这条边的序号是nEdge;
}

int main()
{
    int n,m;//n个点，m条边
    int a,b,c;
    while(~scanf("%d%d",&n,&m))
    {
        memset(p,0,sizeof(p));
        //初始化连接每个点的边的序号都是0，因为这个时候还没有边
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            //a点到b点权重为c的边
            addEdge(a,b,c);
            //有向图，所以a->b,只是a到b，b不能到a;
            //addEdge(b,a,c);如果是无向图，就加上这一句，添加b->a的边
        }
        //输出边，一共有n个点，把从这个点出发的边分别输出出来。
        for(int i = 1; i <= n; i++) 
        {
            printf("第%d个点：\n",i);
            //遍历从i点出发的边的时候，是从最后一条边开始遍历，直到第一条边
            for(int j = p[i]; j; j = e[j].pre) 
            {
                printf("%d->%d,权重：%d\n",i,e[j].v,e[j].w);
            }
        }
    }
    return 0;
}

代码作者：optimjie

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

// 稀疏图用邻接表来存
int h[N], e[N], ne[N], idx;
int w[N]; // 用来存权重
int dist[N];
bool st[N]; // 如果为true说明这个点的最短路径已经确定

int n, m;

void add(int x, int y, int c)
{
    w[idx] = c; 
    // 有重边也不要紧，假设1->2有权重为2和3的边，再遍历到点1的时候
    //2号点的距离会更新两次放入堆中
    e[idx] = y; 
    // 这样堆中会有很多冗余的点，但是在弹出的时候还是会弹出最小值
    //2+x（x为之前确定的最短路径）
    ne[idx] = h[x]; 
    // 标记st为true，所以下一次弹出3+x会continue不会向下执行。
    h[x] = idx++;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[0] = 1;
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 定义一个小根堆
    // 这里heap中为什么要存pair呢，
    // 首先小根堆是根据距离来排的，所以有一个变量要是距离，其次在从堆中拿出来的时    
    // 候要知道知道这个点是哪个点，不然怎么更新邻接点呢？所以第二个变量要存点。
    heap.push({ 0, 1 }); 
    // 这个顺序不能倒，pair排序时是先根据first，再根据second，这里显然要根据距离排序
    while(heap.size())
    {
        PII k = heap.top(); // 取不在集合S中距离最短的点
        heap.pop();
        int ver = k.second, distance = k.first;

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

        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i]; // i只是个下标，e中在存的是i这个下标对应的点。
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({ dist[j], j });
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);

    while (m--)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        add(x, y, c);
    }

    cout << dijkstra() << endl;

    return 0;
}