hihocoder 1093 SPFA算法

　　题目链接：http://hihocoder.com/problemset/problem/1093 , 最短路的SPFA算法。

　　由于点的限制(10w)，只能用邻接表。今天也学了一种邻接表的写法，感觉挺简单。

---

　　SPFA算法其实就是用了BFS的思想，不过和BFS有所不同，SPFA算法中每个顶点可以多次加入到队列中而BFS只能加入一次。我是参考了别人的博客才弄明白这点，学习了别人的东西就要帮忙传播，附上链接：http://www.cnblogs.com/devtang/archive/2011/08/25/spfa.html　

#include <iostream>

#include <cstdio>

#include <vector>

#include <queue>

#include <cmath>

#include <string>

#include <string.h>

#include <algorithm>

using namespace std;

#define LL __int64

#define eps 1e-8

#define INF 1e8

#define lson l , m , rt << 1

#define rson m + 1 , r , rt << 1 | 1

const int MOD = ;

const int maxn =  + ;

struct Edge {

    int v , w;

};

vector <Edge> e[maxn];

int vis[maxn] , dist[maxn];

void SPFA(int s , int n)

{

    for(int i =  ; i <= n ; i++) {

        dist[i] = INF;

        vis[i] = ;

    }

    queue <int> que;

    que.push(s);

    dist[s] = ;

    vis[s] = ;

    while(!que.empty()) {

        int u = que.front();

        for(int i =  ; i < e[u].size() ; i++) {

            int j = e[u][i].v;

            if(dist[u] + e[u][i].w < dist[j]) {

                dist[j] = dist[u] + e[u][i].w;

                if(!vis[j]) {

                    que.push(j);

                    vis[j] = ;

                }

            }

        }

        que.pop();

        vis[u] = ;

    }

}

int main()

{

    int n , m , s , t , u , v , w;

    scanf("%d %d %d %d" , &n , &m , &s , &t);while(m--) {

        scanf("%d %d %d" , &u , &v , &w);

        Edge tmp = {v , w};

        e[u].push_back(tmp);

        tmp.v = u;

        e[v].push_back(tmp);

    }

    SPFA(s , n);

    printf("%d\n" , dist[t]);

    return ;

}