# Poj Solution 2679

```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];
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;
}
}

for( i=0; i<n; i++ )
{
for( j=0; j<n; j++ )
if( e[i][j].fee == fee[i] )
{
}
}

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;

{
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;
}

```
This entry was posted in poj. Bookmark the permalink.