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