用了迭代法,但是有人说用DJ可以过的。
#include <stdio.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int LEN = 1005;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAX = 0x7fffffff;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int map[LEN][LEN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void init ( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for ( int j=0; j<n; j++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( i == j )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
map[i][j] = 0;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
map[i][j] = MAX;
}
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int minest ( int a, int b )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return a < b ? a : b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int cost[LEN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int bellman_ford ( int s, int t, int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int v, u;
int flag = 1;
for ( v=0; v<n; v++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cost[v] = map[s][v];
}
while ( flag )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
flag = 0;
for ( v=0; v<n; v++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for ( u=0; u<n; u++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( map[u][v] < MAX && cost[u] < MAX )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int min = minest ( map[u][v], cost[u] );
if ( cost[v] < min || cost[v] == MAX )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cost[v] = min;
flag = 1;
}
}
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return cost[t];
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int t;
int n, m;
int b, e, len;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while ( scanf ( "%d", &t ) != EOF )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for ( int i=1; i<=t; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf ( "%d%d", &n, &m );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
init ( n );
for ( int j=0; j<m; j++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf ( "%d%d%d", &b, &e, &len );
map[b-1][e-1] = len;
map[e-1][b-1] = len;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf ( "Scenario #%d:\n%d\n\n", i, bellman_ford ( 0, n-1, n ) );
}
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1797