http://poj.org/problem?id=2679
#include <stdio.h>
#include <vector>
#include <memory.h>
using namespace std;
const int size = 1110;
struct edge
{
int len;
int fee;
edge *next;
};
edge e[size][size];
edge *link[size];
bool sign[size];
int m, n, begin, end;
int fee[size];
void search( int b )
{
int a;
sign[b] = true;
for( a=0; a<n; a++ )
if( !sign[a] && e[a][b].fee == fee[a] )
search( a );
}
bool init( )
{
int i, j, u, v, f1, f2, l;
if( scanf( "%d %d %d %d", &n, &m, &begin, &end ) != 4 )
return false;
for( i=0; i<n; i++ )
{
fee[i] = 800;
for( j=0; j<n; j++ )
e[i][j].fee = 999;
}
char c[10];
for( i=0; i<m; i++ )
{
scanf( "%1s", c );
scanf( "%d,%d,%d[%d]%d)", &u, &v, &f1, &l, &f2 );
if( e[u][v].fee > f1 || ( e[u][v].fee == f1 && e[u][v].len > l ) )
{
e[u][v].fee = f1, e[u][v].len = l;
if( fee[u] > f1 ) fee[u] = f1;
}
if( e[v][u].fee > f2 || ( e[v][u].fee == f2 && e[v][u].len > l ) )
{
e[v][u].fee = f2, e[v][u].len = l;
if( fee[v] > f2 ) fee[v] = f2;
}
}
memset( link, 0, sizeof link );
for( i=0; i<n; i++ )
{
for( j=0; j<n; j++ )
if( e[i][j].fee == fee[i] )
{
e[i][j].next = link[i];
link[i] = &e[i][j];
}
}
memset( sign, 0, sizeof sign );
search( end );
return true;
}
int dis[size];
int len[size];
bool flag[size];
int dijstra( )
{
int i, j, k, t;
edge *p;
memset( flag, 0, sizeof flag );
for( i=0; i<n; i++ )
len[i] = 999999;
len[begin] = 0;
for( i=0; i<n; i++ )
{
k = end;
for( j=0; j<n; j++ )
if( sign[j] && !flag[j] && len[j] < len[k] )
k = j;
if( k == end )
return len[k];
flag[k] = true;
for( p=link[k]; p; p=p->next )
{
j = p-e[k];
if( dis[j] - dis[k] == p->fee && len[j] > ( t = len[k] + p->len ) )
len[j] = t;
}
}
return 0;
}
void doit( )
{
int i, j, t, l;
edge *p;
if( !sign[begin] )
{
printf( "VOIDn" );
return;
}
for( i=0; i<n; i++ )
dis[i] = 999999;
dis[begin] = 0;
for( i=0; i<n-1; i++ )
{
for( j=0; j<n; j++ )
if( sign[j] )
{
for( p = link[j]; p; p=p->next )
if( ( t = dis[j] + p->fee ) < dis[ l=p-e[j] ] )
dis[l] = t;
}
}
for( j=0; j<n; j++ )
if( sign[j] )
{
for( p = link[j]; p; p=p->next )
if( sign[ l=p-e[j] ] && dis[j]+p->fee < dis[l] )
break;
if( p ) break;
}
if( p )
{
printf( "UNBOUNDn" );
return;
}
printf( "%d %dn", dis[end], dijstra() );
}
int main( )
{
while( init( ) )
doit( );
return 0;
}