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