热浪
FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 <= T <= 2,500)个城镇，方便地标号為1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用（包括油费，过路费等等）。考虑这个有7个城镇的地图。城镇5是奶源，城镇4是终点（括号内的数字是道路的通过费用）。
[1]----1---[3]-
/ \
[3]---6---[4]---3--[3]--4
/ / /|
5 --[3]-- --[2]- |
\ / / |
[5]---7---[2]--2---[3]---
| /
[1]------
经过路线5-6-3-4总共需要花费3 (5->6) + 4 (6->3) + 3 (3->4) = 10的费用。
给定一个地图，包含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)最小的总费用。
* 第2到第C+1行: 第i+1行描述第i条道路。有3个由空格隔开的整数: Rs, Re和Ci
——译者注）数据保证至少存在一条道路。
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
样例输出 SampleOutput [复制数据]
7
#include<stdio.h>
#include<stdbool.h>
#include<limits.h>
int
a[],b[],c[],q[],d[],f[];
bool
vis[]={false};
int
x,y,z,sum,n,m,i,s,t; void
qsort(int head, int tail)
{
int
i,j,x,y,z;
i=head;j=tail;
x=a[head];y=b[head];z=c[head];
while(i<j)
{
while((i<j)&&(a[j]>=x)) j--;
a[i]=a[j];b[i]=b[j];c[i]=c[j];
while((i<j)&&(a[i]<=x)) i++;
a[j]=a[i];b[j]=b[i];c[j]=c[i];
}
a[i]=x;b[i]=y;c[i]=z;
if (head<(i-)) qsort(head,i-);
if ((i+)<tail) qsort(i+,tail);
} void
spfa(int s)
{
int
i,k,head,tail;
for (i=;i<=n;i++)
d[i]=INT_MAX >> ;
d[s]=;
head=;tail=;
q[]=s;
vis[s]=true; while (head<tail)
{
head=head%+;
k=q[head];
for (i=f[k];i<=(f[k+]-);i++)
if ((d[k]+c[i])<d[b[i]])
{
d[b[i]]=d[k]+c[i];
if (vis[b[i]]==false)
{
tail=tail%+;
q[tail]=b[i];
vis[b[i]]=true;
}
}
vis[k]=false;
}
} int
main(void)
{
scanf("%d%d%d%d\n",&n,&m,&s,&t);
sum=;
for(i=;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
sum++;
a[sum]=x;
b[sum]=y;
c[sum]=z;
sum++;
b[sum]=x;
a[sum]=y;
c[sum]=z;
}
m=m*;
qsort(,m);
for(i=;i<=m;i++)
if (f[a[i]]==) f[a[i]]=i;
f[n+]=m+;
for (i=n;i>=;i--)
if (f[i]==) f[i]=f[i+];
spfa(s);
printf("%d\n",d[t]);
return ;
}