简单的递归DFS+邻接矩阵，一直WA，所以也没有剪枝。求变态数据，求帮助啊大神们，实在搞不定了，discuss中的全部数据过了两遍，讨论帖子从头看到尾一篇都没漏，但是还是实在看不出来错误啊。

#include <stdio.h>
#include <string.h>

#define MAXNUM 105
#define MAX 65535

int gwLevelgap; //等级差
int gwMax; //最大物品数
int gwTotal = MAX; //记录最优解
int gawRouteMap[MAXNUM][MAXNUM]; //邻接矩阵，路权为优惠价格
int gawLevel[MAXNUM]; //记录每一个节点的等级
int gawPrice[MAXNUM]; //记录每一个节点的直接购买价格
int gawRecord[MAXNUM]; //记录是否已经交易过，避免形成了环

void GetInput()
{
    int i = 0;
    int j = 0;
    int wPrice = 0;
    int wLevel = 0;
    int wExcNum = 0;
    int wNo = 0;
    int wRoutePrice = 0;
    scanf("%d %d", &gwLevelgap, &gwMax);
    for(i=0; i<gwMax; i++)
    {
        scanf("%d %d %d", &wPrice, &wLevel, &wExcNum);
        gawLevel[i] = wLevel;
        gawPrice[i] = wPrice;
        for(j=0; j<wExcNum; j++)
        {
            scanf("%d %d", &wNo, &wRoutePrice);
            gawRouteMap[i][wNo-1] = wRoutePrice;
        }
    }
}

int CalcPrice(int j, int sum, int maxlevel, int minlevel)
{
    int i = 0;
    int all0flag = 1;
    if(j > gwMax-1)
        return 0;
    if(gawRecord[j] == 1)
    {
        return 1;
    }
    gawRecord[j] = 1;
    if(gawLevel[j] > maxlevel)
        maxlevel = gawLevel[j];
    if(gawLevel[j] < minlevel)
        minlevel = gawLevel[j];
    if(maxlevel - minlevel > gwLevelgap)
    {
        return 1;
    }
    for(i=0; i<gwMax; i++)
    {
        if(gawRouteMap[j][i] != -1)
        {
            if(1 == CalcPrice(i, sum+gawRouteMap[j][i], maxlevel, minlevel))
                if(sum + gawPrice[j] < gwTotal)
                    gwTotal = sum + gawPrice[j];
            if(j == 0)
            {
                memset(gawRecord, 0, MAXNUM*sizeof(int));
                gawRecord[j] = 1;
            }
            all0flag = 0;
        }
    }
    if(all0flag == 1)
    {
        sum += gawPrice[j];
        if(sum < gwTotal)
            gwTotal = sum;
    }
    return 0;
}

int main(void)
{
    memset(gawRouteMap, -1, MAXNUM*MAXNUM*sizeof(int));
    GetInput();
    gwTotal = gawPrice[0];
    CalcPrice(0, 0, gawLevel[0], gawLevel[0]);
    printf("%d\n", gwTotal);

    return 0;
}

• Re:Discuss中的数据全过，但是还是WA，求帮助啊，大神们 (2372) liuke5134 2017-05-09 15:40:29