POJ2387TiltheCowsComeHome(Spfa)

题意&＃xff1a;一头奶牛沿着路标回家&＃xff0c;求最短路径。
题解&＃xff1a;注意处理重边。感觉不错&＃xff0c;以后对于无向图就用vector构图&＃xff0c;可以省去对重边的处理。对于有向图用记录头结点的边的方式构图。

#include
#include
#include
using namespace std;
#define MAX 10000
#define INF 9999999
struct Edge { int v, w, next; };
Edge edge[MAX];
int head[MAX], E;
int d[MAX], inque[MAX];
void spfa ( int n )
{
int u, v, i;
for ( i &＃61; 1; i <&＃61; n; i&＃43;&＃43; )
d[i] &＃61; INF, inque[i] &＃61; 0;
d[n] &＃61; 0;
queue que;
que.push(n);
inque[n] &＃61; true;
while ( que.empty() &＃61;&＃61; false )
{
u &＃61; que.front();
que.pop(); inque[u] &＃61; false;
for (i &＃61; head[u]; i !&＃61; -1; i &＃61; edge[i].next)
{
v &＃61; edge[i].v;
if ( d[v] > d[u] &＃43; edge[i].w )
{
d[v] &＃61; d[u] &＃43; edge[i].w;
if ( inque[v] ) continue;
inque[v] &＃61; true;
que.push(v);
}
}
}
}
void add ( int u, int v, int w )
{
edge[E].v &＃61; v;
edge[E].w &＃61; w;
edge[E].next &＃61; head[u];
head[u] &＃61; E&＃43;&＃43;;
}
int main()
{
int T, N, u, v, w;
scanf("%d%d",&T,&N);
memset(head,-1,sizeof(head));
E &＃61; 0;
while ( T-- )
{
scanf("%d%d%d",&u,&v,&w);
add ( u, v, w );
add ( v, u, w );
}
spfa ( N );
printf("%d\n",d[1]);
return 0;
}