用了迭代法,但是有人说用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