学步园

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

#include<cstdio>
#include<queue>
#include<cstring>
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 = 1; i <= n; i++ )
        d[i] = INF, inque[i] = 0;
    d[n] = 0;
    queue<int> que;
    que.push(n);
    inque[n] = true;
    while ( que.empty() == false )
    {
        u = que.front();
        que.pop(); inque[u] = false;
        for (i = head[u]; i != -1; i = edge[i].next)
        {
            v = edge[i].v;
            if ( d[v] > d[u] + edge[i].w )
            {
                d[v] = d[u] + edge[i].w;
                if ( inque[v] ) continue;
                inque[v] = true;
                que.push(v);
            }
        }
    }
}

void add ( int u, int v, int w )
{
    edge[E].v = v;
    edge[E].w = w;
    edge[E].next = head[u];
    head[u] = E++;
}

int main()
{
    int T, N, u, v, w;
    scanf("%d%d",&T,&N);
    memset(head,-1,sizeof(head));
    E = 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;
}