用了迭代法，但是有人说用DJ可以过的。

#include <stdio.h>

const int LEN = 1005;

const int MAX = 0x7fffffff;

int map[LEN][LEN];

void init ( int n )
{

    for ( int i=0; i<n; i++ )
    {
        for ( int j=0; j<n; j++ )
        {
            if ( i == j )
            {
                map[i][j] = 0;
            }
            else
            {
                map[i][j] = MAX;
            }
        }
    }
}

int minest ( int a, int b )
{

    return a < b ? a : b;
}

int cost[LEN];

int bellman_ford ( int s, int t, int n )
{
    
    int v, u;
    int flag = 1;
    
    for ( v=0; v<n; v++ )
    {
        cost[v] = map[s][v];
    }
    
    while ( flag )
    {
        flag = 0;
        for ( v=0; v<n; v++ )
        {
            for ( u=0; u<n; u++ )
            {
                if ( map[u][v] < MAX && cost[u] < MAX )
                {
                    int min = minest ( map[u][v], cost[u] );
                    if ( cost[v] < min || cost[v] == MAX )
                    {
                        cost[v] = min;
                        flag = 1;
                    }
                }
            }
        }
    }

    return cost[t];
}

int main ()
{

    int t;
    int n, m;
    int b, e, len;

    while ( scanf ( "%d", &t ) != EOF )
    {
        for ( int i=1; i<=t; i++ )
        {
            scanf ( "%d%d", &n, &m );

            init ( n );
            for ( int j=0; j<m; j++ )
            {
                scanf ( "%d%d%d", &b, &e, &len );
                map[b-1][e-1] = len;
                map[e-1][b-1] = len;
            }

            printf ( "Scenario #%d:\n%d\n\n", i, bellman_ford ( 0, n-1, n ) );
        }
    }
    return 0;
}

地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1797