题目链接：http://hihocoder.com/problemset/problem/1081
SPFA求最短路，是不应-羁绊大神教我的，附上头像。
我第一次写SPFA，我用的vector存邻接表，以后也会保持这种习惯。每个元素是一个pair类型，分别表示可连接的点，和权值。
SPFA：把起点放到队列，扫一遍可以链接的点，每一次松弛条件是：dist[next.first] = min(dist[next.first],dist[f]+next.second);就是说J—>S或者J—>K—>S;把没有访问过的点再次放到队列中去，继续更新没有访问的点，直至结束。
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <string>
#include <queue>
#include <map>
#include <cmath> using namespace std; typedef pair<int,int> pii; int spfa(vector<vector<pii> >& vadj, int nv, int sbeg, int send)
{
int dist[nv];
int a; for(a=;a<nv;++a)
dist[a]=;
dist[sbeg]=; bool vis[nv];
memset(vis,,sizeof(vis));
vis[sbeg]=true; queue<int>Q;
Q.push(sbeg); int ifrt;
pii next; while(Q.size())
{
ifrt=Q.front();
Q.pop();
vis[ifrt]=false; for(a=;a<vadj[ifrt].size();++a)
{
next=vadj[ifrt][a];
if(dist[next.first]>dist[ifrt]+next.second)
{
dist[next.first]=dist[ifrt]+next.second;
if(!vis[next.first])
{
Q.push(next.first);
vis[next.first]=true;
}
}
}
} return dist[send];
} int main()
{
int nv,ne;
int ibeg,iend;
int sa,sb,sd;
int a; cin>>nv>>ne;
cin>>ibeg>>iend; --ibeg;
--iend; vector<vector<pii> > vadj(nv); for(a=;a<ne;++a)
{
scanf("%d %d %d",&sa,&sb,&sd);
--sa;
--sb;
vadj[sa].push_back(make_pair(sb,sd));
vadj[sb].push_back(make_pair(sa,sd));
} cout<<spfa(vadj,nv,ibeg,iend)<<endl; return ;
}