最短路算法（SPFA）

   SPFA算法（Shortest Path Faster Algorithm），也是求解单源最短路径问题的一种算法，用来解决：给定一个加权有向图G和源点s，对于图G中的任意一点v，求从s到v的最短路径。 SPFA算法是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算，他的基本算法和Bellman-Ford一样，并且用如下的方法改进： 1、第二步，不是枚举所有节点，而是通过队列来进行优化 设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。 2、同时除了通过判断队列是否为空来结束循环，还可以通过下面的方法： 判断有无负环：如果某个点进入队列的次数超过V次则存在负环（SPFA无法处理带负环的图）。（来自NOCOW）

HDU 2544 模板测试专用

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>

//邻接表储存比较好，时间和空间效率上都优于矩阵，不过实现略微复杂
struct node{
    int end, weight;
    node *next;
};

const int inf = 0xfffff;
node ver[200];
int n, m;							//n为顶点数，m为边数
int dis[200], vis[200], count[200];	//count记录顶点入队列次数，若一个顶点入队大于n次，则存在负环

void insert(int a, int b, int w){
    node *p = (node *)malloc(sizeof(node));
    p->end = b, p->weight = w;
    p->next = ver[a].next;
    ver[a].next = p;
}

void initi(int n){
    int i;
    dis[1] = 0;       				//1作为起点
    memset(vis, 0, sizeof(vis));
    memset(count, 0, sizeof(count));
    ver[1].next = NULL;
    for (i = 2;i <= n;i++){
        dis[i] = inf;
        ver[i].next = NULL;
    }
}

int SPFA(){
    std::queue<int> p;
    p.push(1);
    count[1]++;
    vis[1] = 1;
    while (!p.empty()){
        int s = p.front();
        p.pop();
        vis[s] = 0;
        for (node *q = ver[s].next;q != NULL;q = q->next)	//对出队元素进行松弛
            if (dis[q->end] > dis[s] + q->weight){
                dis[q->end] = dis[s] + q->weight;
                if(!vis[(q->end)]){
          	 	p.push(q->end);
       	 		 vis[(q->end)] = 1;
                	count[q->end]++;
                }
                if (count[q->end] > n) 			//判断是否存在负环
                    return -1;
            }
    }
    return dis[n];
}

int main(){
    while (scanf("%d%d", &n, &m)){
        int i,a,b,w;
        if (n == 0&&m == 0)
            break;
        initi(n);
        for (i = 0;i < m;i++){
            scanf("%d%d%d", &a, &b, &w);
            insert(a, b, w);
            insert(b, a, w);
        }
        printf("%d\n", SPFA());
    }
    return 0;
}
           

静态链表版（模拟链表），用个namespace封装比较好

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

const int N = 101;
const int INF = 0xfffff;
int n, m;

namespace graph{
	struct SPFA{
	    int dis[N], vis[N], head[N], it, cnt;
	    struct node{
	        int end, weight;
	        int next;
	    }edge[N * N];
	    void addedge(int a, int b, int w){
	    	edge[cnt].end = b;
	        edge[cnt].weight = w;
	        edge[cnt].next = head[a];
	        head[a] = cnt++;
	    }
	    void initi(int n, int start){
	        int i;
	        cnt = 0;
	        memset(vis, 0, sizeof(vis));
	        memset(head, -1, sizeof(head));
	        for(i = 1;i <= n;i++)
	            dis[i] = INF; 
	        dis[start] = 0;
	    }
	    int shortest_path(int start, int end){
	        queue<int> p;
	        p.push(start);
	        vis[start] = 1;
	        while(!p.empty()){
	            int s = p.front();
	            p.pop();
	            vis[s] = 0;
	            for(it = head[s];it != -1;it = edge[it].next){
	                int to = edge[it].end;
	                if(dis[to] > dis[s] + edge[it].weight){
	                    dis[to] = dis[s]+edge[it].weight;
	                    if(!vis[to]){
	                	    p.push(to);
	                    	vis[to] = 1;
	                    }
	                }
	            }
	        }
	        return dis[end];
	    }
	}g;
}

int main(){
    int n, m;
    while(cin >> n >> m){
        int i, a, b, w;
        if(!n&&!m)
            break;
        graph::g.initi(n, 1);
        for(i = 0;i < m;i++){
            scanf("%d%d%d", &a, &b, &w);
            graph::g.addedge(a, b, w);
            graph::g.addedge(b, a, w);
        }
        cout << graph::g.shortest_path(1, n) << endl;
    }
    return 0;
}