热浪解题报告（SPFA）

德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。Farmer John此时以先天下之忧而忧，后天下之乐而乐的精神，身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 <= T <= 2,500)个城镇，方便地标号為1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用（包括油费，过路费等等）。

给定一个地图，包含C (1 <= C <= 6,200)条直接连接2个城镇的道路。每条道路由道路的起点Rs，终点Re (1 <= Rs <= T; 1 <= Re <= T)，和花费(1 <= Ci <= 1,000)组成。求从起始的城镇Ts (1 <= Ts <= T)到终点的城镇Te(1 <= Te <= T)最小的总费用。

问题显然是一个最短路问题代码如下：

#include
using namespace std;

const int MAXN=25000;
const int INF=1<<30;
struct edge{
int to,next,w;
}e[MAXN];
int d[MAXN];
int head[MAXN],cnt=0;
inline void add(int u,int v,int w){e[++cnt]=(edge){v,head[u],w},head[u]=cnt;}
int t,c,g,v;
int main()
{
queueq;
bool sw[MAXN];
memset(sw,0,sizeof(sw));
memset(head,-1,sizeof(head));
cin>>t>>c>>g>>v;
for(int i=1;i<=t;i++)d[i]=INF;
int x1,x2,x3;
for(int i=1;i<=c;i++)
{
cin>>x1>>x2>>x3;
add(x1,x2,x3);
add(x2,x1,x3);
}
d[g]=0;q.push(g);sw[g]=1;
while(!q.empty()){
int u=q.front();q.pop();sw[u]=0;
for(int i=head[u];i;i=e[i].next)
{ int v=e[i].to,w=e[i].w;
if(d[v]>d[u]+w)
{
d[v]=d[u]+w;
if(!sw[v])
{
q.push(v);
}
}
}
}
printf("%d",d[v]);
return 0;
}