ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1004. Sightseeing Trip

Dijkstra algo meet WA#1.need someone to review my code.
Posted by itm94lj 20 Jul 2016 10:03
try dijkstra to solve this problem. pass all tests found.
but meet WA#1. try to review code several times but cann't figure out why.
code is here if you found why pls reply.tks
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_VERT_NUM 100
#define BIT_SET(a, b) (a|=b)
#define BIT_RESET(a, b) (a&=(~b))
#define BIT_TEST(a, b) (0!=(a&b))

#define EDGE_TAG_PROCED 0x01

typedef struct tagEDGE{
    struct tagEDGE *pstNext;
    int iEnd;
    long iWeight;
    unsigned char ucFlag;
}EDGE_S;

#define VERT_TAG_PROCED 0x01
typedef struct tagVERT{
    EDGE_S *pstEdge;
    long iPathLen;
    int iPathNodeNum;
    int aiPathNode[MAX_VERT_NUM];
    unsigned char ucFlag;
}VERT_S;

void addEdgeNode(VERT_S *pstVert, int iFrom, int iTo, long iWeight)
{
    EDGE_S *pstEdge = NULL;

    pstEdge = pstVert[iFrom].pstEdge;
    while (NULL != pstEdge)
    {
        if (iTo == pstEdge->iEnd)
        {
            if (pstEdge->iWeight > iWeight)
            {
                pstEdge->iWeight = iWeight;
            }
            return ;
        }
        pstEdge = pstEdge->pstNext;
    }

    pstEdge = malloc(sizeof(EDGE_S));
    if (NULL != pstEdge)
    {
        memset(pstEdge, 0, sizeof(EDGE_S));
        pstEdge->iEnd    = iTo;
        pstEdge->iWeight = iWeight;
        if (NULL == pstVert[iFrom].pstEdge)
        {
            pstVert[iFrom].pstEdge = pstEdge;
        }
        else
        {
            pstEdge->pstNext = pstVert[iFrom].pstEdge;
            pstVert[iFrom].pstEdge = pstEdge;
        }
    }

    return ;
}

void AddEdge(VERT_S *pstVert, int iFrom, int iTo, long iWeight)
{
    addEdgeNode(pstVert, iFrom, iTo, iWeight);
    addEdgeNode(pstVert, iTo, iFrom, iWeight);

    return ;
}

void init(VERT_S *pstVert)
{
    int i=0;
    memset(pstVert, 0, MAX_VERT_NUM*sizeof(VERT_S));
    for (i=0; i<MAX_VERT_NUM; i++)
    {
        pstVert[i].iPathLen = LONG_MAX;
    }

    return ;
}

void relax(VERT_S *pstVert, int iFrom, int iTo, EDGE_S *pstEdge)
{
    VERT_S *pstFromVert = NULL, *pstToVert = NULL;

    pstFromVert = &pstVert[iFrom];
    pstToVert   = &pstVert[iTo];

    if (pstToVert->iPathLen > pstFromVert->iPathLen + pstEdge->iWeight)
    {
        pstToVert->iPathLen = pstFromVert->iPathLen + pstEdge->iWeight;
        pstToVert->iPathNodeNum = pstFromVert->iPathNodeNum+1;
        memcpy(pstToVert->aiPathNode,
               pstFromVert->aiPathNode,
               sizeof(pstFromVert->aiPathNode));
        pstToVert->aiPathNode[pstFromVert->iPathNodeNum] = iTo;
    }

    return ;
}

int foundMinVert(VERT_S *pstVert)
{
    int iMinVert = -1, i=0;

    for (i=0; i<MAX_VERT_NUM; i++)
    {
        if (!BIT_TEST(pstVert[i].ucFlag, VERT_TAG_PROCED) &&
            (LONG_MAX > pstVert[i].iPathLen))
        {
            if (-1 == iMinVert)
            {
                iMinVert = i;
            }
            else
            {
                if (pstVert[i].iPathLen < pstVert[iMinVert].iPathLen)
                {
                    iMinVert = i;
                }
            }
        }
    }

    return iMinVert;
}

void calcShortPath(VERT_S *pstVert, int iSource)
{
    int i=0, iFrom=0, iTo=0, iMinVert = -1;
    VERT_S *pstCurVert = NULL, *pstEndVert=NULL;
    EDGE_S *pstEdge = NULL;

    pstCurVert = &pstVert[iSource];
    pstCurVert->iPathLen = 0;
    BIT_SET(pstCurVert->ucFlag, VERT_TAG_PROCED);
    iFrom = iSource;
    pstCurVert->iPathNodeNum = 1;
    pstCurVert->aiPathNode[0] = iSource;
    for (i=0; i<MAX_VERT_NUM; i++)
    {
        pstEdge = pstCurVert->pstEdge;
        while (NULL != pstEdge)
        {
            iTo = pstEdge->iEnd;
            if ((!BIT_TEST(pstVert[iTo].ucFlag, VERT_TAG_PROCED)) &&
                (!BIT_TEST(pstEdge->ucFlag, EDGE_TAG_PROCED)))
            {
                relax(pstVert, iFrom, iTo, pstEdge);
            }
            pstEdge = pstEdge->pstNext;
        }
        iFrom = foundMinVert(pstVert);
        if (-1 != iFrom)
        {
            BIT_SET(pstVert[iFrom].ucFlag, VERT_TAG_PROCED);
            pstCurVert = &pstVert[iFrom];
        }
        else
        {
            break;
        }
    }

    return ;
}

void reset(VERT_S *pstVert)
{
    int i=0;

    for (i=0; i<MAX_VERT_NUM; i++)
    {
        pstVert[i].ucFlag = 0;
        pstVert[i].iPathLen = LONG_MAX;
        pstVert[i].iPathNodeNum = 0;
        memset(pstVert[i].aiPathNode, 0, sizeof(pstVert[i].aiPathNode));
    }

    return ;
}

void setEdgeNodeFlag(VERT_S *pstVert, int iFrom, int iTo, unsigned char ucFlag)
{
    EDGE_S *pstEdge = NULL;

    pstEdge = pstVert[iFrom].pstEdge;
    while (NULL != pstEdge)
    {
        if (iTo == pstEdge->iEnd)
        {
            BIT_SET(pstEdge->ucFlag, ucFlag);
        }
        pstEdge = pstEdge->pstNext;
    }

    return ;
}

void setEdgeFlag(VERT_S *pstVert, int iFrom, int iTo, unsigned char ucFlag)
{
    setEdgeNodeFlag(pstVert, iFrom, iTo, ucFlag);
    setEdgeNodeFlag(pstVert, iTo, iFrom, ucFlag);

    return ;
}

void resetEdgeNodeFlag(VERT_S *pstVert, int iFrom, int iTo, unsigned char ucFlag)
{
    EDGE_S *pstEdge = NULL;

    pstEdge = pstVert[iFrom].pstEdge;
    while (NULL != pstEdge)
    {
        if (iTo == pstEdge->iEnd)
        {
            BIT_RESET(pstEdge->ucFlag, ucFlag);
        }
        pstEdge = pstEdge->pstNext;
    }

    return ;
}

void resetEdgeFlag(VERT_S *pstVert, int iFrom, int iTo, unsigned char ucFlag)
{
    resetEdgeNodeFlag(pstVert, iFrom, iTo, ucFlag);
    resetEdgeNodeFlag(pstVert, iTo, iFrom, ucFlag);

    return ;
}

void freeall(VERT_S *pstVert)
{
    int i=0;
    EDGE_S *pstEdge = NULL, *pstFree = NULL;

    for (i=0; i<MAX_VERT_NUM; i++)
    {
        pstEdge = pstVert[i].pstEdge;
        while (NULL != pstEdge)
        {
            pstFree = pstEdge;
            pstEdge = pstEdge->pstNext;
            free(pstFree);
        }
    }

    return ;
}

int main()
{
    int iCross=0, iRoad = 0;
    int i=0, iFrom=0, iTo=0,  j=0;
    long iWeight=0;
    VERT_S astVert[MAX_VERT_NUM];
    EDGE_S *pstEdge = NULL;
    int  iMinPathNode = 0;
    long iMinPathLen = -1;
    int aiMinPath[MAX_VERT_NUM];

    scanf("%d", &iCross);
    while ((-1 != iCross))
    {
        scanf("%d", &iRoad);
        init(astVert);
        iMinPathNode = 0;
        iMinPathLen = LONG_MAX;
        memset(aiMinPath, 0, sizeof(aiMinPath));
        for (i=0; i<iRoad; i++)
        {
            scanf("%d %d %ld", &iFrom, &iTo, &iWeight);
            AddEdge(astVert, iFrom-1, iTo-1, iWeight);
        }

        for (i=0; i<MAX_VERT_NUM; i++)
        {
            iFrom = i;
            pstEdge = astVert[i].pstEdge;
            while (NULL != pstEdge)
            {
                iTo = pstEdge->iEnd;
                setEdgeFlag(astVert, iFrom, iTo, EDGE_TAG_PROCED);
                calcShortPath(astVert, iFrom);

                if (iMinPathLen >
                    (astVert[iTo].iPathLen + pstEdge->iWeight))
                {
                    iMinPathLen = astVert[iTo].iPathLen + pstEdge->iWeight ;
                    iMinPathNode = astVert[iTo].iPathNodeNum;
                    memcpy(aiMinPath, astVert[iTo].aiPathNode, sizeof(aiMinPath));
                }

                resetEdgeFlag(astVert, iFrom, iTo, EDGE_TAG_PROCED);
                reset(astVert);
                pstEdge = pstEdge->pstNext;
            }
        }

        freeall(astVert);

        if (LONG_MAX == iMinPathLen)
        {
            printf("No solution.\r\n");
        }
        else
        {
            for (i=0; i<iMinPathNode; i++)
            {
                printf("%d ", aiMinPath[i]+1);
            }
            printf("\r\n");
        }

        scanf("%d", &iCross);
    }//while

    return 0;
}