蓝桥杯 - 算法训练 - ALGO - 5 最短路（spfa）

小记： 在提交的时候 提交了4次，第一次有一句代码没删 RE，第二次 70分，边数又开小了忘记乘以10，第三次，最短距离数组的初始化赋值太小了，唉~ 真是差劲，一路下来，一个感觉秒过的题，历经了波澜曲折，汲取经验，下次不再重犯。

思路：spfa，单源最短路径算法，采取队列维护，这里没有优化，spfa的详细讲解：nocow

一、从起点开始更新与其相连的点的最短距离数组值，更新了的，没有入队的就入队。

二、从队列取队首的节点，然后更新其相连的点的权值，若是能更新，则看其是否已入队，没入队则入队

三、继续第二步。直至队空。

四、返回答案

优化策略：

SLF：Small Label First 策略。


实现方法是，设队首元素为 i，队列中要加入节点 j，在 d[i]<=d[j] 时加到队首而不是队尾，否则和普通的 SPFA 一样加到队尾。



LLL：Large Label Last 策略。


实现方法是，设队列 Q 中的队首元素为i，距离标号的平均值为 d_=(Vj属于Q，所有d[j]值的和，除以Q里元素的个数)，每次出队时，若 d[i]>平均值，把 i 移到队列末尾，如此反复，直到找到一个 i 使  d[i]>=平均值，将其出队。

spfa可以判负环。对某点入队的次数进行判定，若大于节点数就存在负环。

O（Ke）k通常情况下不大于2，e为边数

这里代码是使用邻接表的数组形式实现的，因为n，m的数量级太大所以不能用邻接矩阵形式。 数组实现的邻接表 和 前向星 很相似 

代码：

//#pragma comment(linker, "/STACK:102400000,102400000")
#include <string.h>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAX_ 20010
#define MAX 0x7fffffff
#define max(a,b) ((a>b)?(a):(b))


struct point {
    int v,cap,next;
} edge[MAX_*10];

int head[MAX_];

int d[MAX_];
bool vis[MAX_];

int M, n, m;



void add(int from, int to, int cap) {
    edge[M].v = to;
    edge[M].cap = cap;
    edge[M].next = head[from];
    head[from] = M++;
}

void spfa(int start){
    queue<int>q;
    for(int i = 0; i <= n; ++i){
        d[i] = MAX;
        vis[i] = 0;
    }
    q.push(start);
    d[start] = 0;
    vis[start] = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for(int i = head[x]; i != -1; i = edge[i].next){
            int v = edge[i].v;
            if(d[v] > d[x] + edge[i].cap){
                d[v] = d[x] + edge[i].cap;
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}

int main() {
    int i;
    int s,t,c;

    while(~scanf("%d%d",&n,&m)) {
        M = 0;
        memset(head,-1,sizeof(head));

        for(i = 0; i < m; i++) {
            scanf("%d%d%d",&s,&t,&c);
            add(s,t,c);
        }
        spfa(1);
        for(i = 2; i <= n; ++i){
            printf("%d",d[i]);
            if(i!=n)printf("\n");
        }
    }
    return 0;
}