dijkstra算法模板：

算法思想：
每一条最短路，其中间节点，到起始节点的路径也为最短路

如果需要打印最短路径，只需要用一个pre数组记录每一点的前驱节点即可

伪代码：

集合S：已确定最短距离的点的集合

1.  初始化，d[s] = 0 , d[i] = INF;
2.  for 循环n次
        找到不在S中的距离最短的点t（反应在代码上就是，未访问的点）；（这一步可以用堆优化）
        将点t加入集合S中；
        以t为中介点，更新t能到达的未访问的点的距离；


邻接矩阵版：
const int N = 10010 , INF = 1e9;
int G[N][N];
int d[N];   //记录最短路
int n,m;    //n个顶点，m条边

void dijkstra(int s)
{
    fill(d,d+N,INF);
    d[s] = 0;           //初始化

    for(int i=0;i<n;i++)        //n次循环
    {
        int u = -1 , MIN = INF;
        for(int i=1;i<=n;i++)       //找到未访问的点(即不在S中的点)距离最短的点u
        {
            if(vis[u] == false && d[u] < MIN)
            {
                u = i;
                MIN = d[u];
            }
        }

        if(u == -1) return;     //说明剩下的点，全部与s不连通

        vis[u] = true;      //加入到已访问集合

        for(int i=1;i<=n;i++)       //更新u能到达的未访问的点的距离
        {
            if(vis[i] == false && G[u][i] != INF && d[u] + G[u][i] < d[i])
            {
                d[i] = d[u] + G[u][i];
            }
        }
    }
}

邻接表版：
struct node{
    int v,w;    //v为节点编号，w为边权
};

vector<node> Adj[N];

void dijkstra(int s)
{
    fill(d,d+N,INF);
    d[s] = 0;       //初始化

    for(int i=0;i<n;i++)
    {
        int u = -1 , MIN = INF;
        for(int i=1;i<=n;i++)       //每次都找未访问的点中距离最短的点
        {
            if(vis[i] == false && d[i] < MIN)
            {
                u = i;
                MIN = d[i];
            }
        }

        if(u == -1) return;     //剩下的点与s不连通

        vis[u] = true;

        for(int i=0;i<Adj[u].size();i++)
        {
            int v = Adj[u][i].v;
            int distance = Adj[u][i].w;
            if(vis[v] == false && d[u] + distance < d[i])
            {
                d[i] = d[u] + distance;
            }
        }
    }

}

打印最短路径的函数：

//打印s到v的最短路径
void dfs(int s,int v)       
{
    if(v == s)
    {
        cout << s  << " ";
        return;
    }

    dfs(s,pre[v]);
    cout << v << " ";
}


三种第二标尺：
1.额外边权
2.点权
3.记录有多少条最短路径

对于第二标尺的问题，只需要在以u为中介点，更新其他点的代码块中进行更改

1.额外边权：用一个数组c[N]，记录从s到点v的最小花费，cost[N][N]记录u到v的花费；

int c[N] , cost[N][N];
for(int v=1;v<=n;v++)
{
    if(vis[v] = false && G[u][v] != INF)
    {
        if(d[u] + G[u][v] < d[v])
        {
            d[v] = d[u] + G[u][v];
            c[v] = c[u] + cost[u][v];
        }else if(d[u] + G[u][v] == d[v] && c[u] + cost[u][v] < c[v])
        {
            c[v] = c[u] + cost[u][v];
        }
    }
}