这里会有内存非法访问吗？一个ACM题的疑惑，崩溃ING-.-

题目在这儿
http://acm.hdu.edu.cn/showproblem.php?pid=2485
我的代码在这，说说大概算法，就是找出每条能够在K时间内到达终点的路线，然后对每条路线经过的station进行统计
一次删掉经过最多的，直至没有剩余可走的路线。

#include <stdio.h>
#include <memory.h>
#define DIS_UNDEF 99999
int check(int *status, int n)
{
    return (status[(n-1)/32] == (status[(n-1)/32] | (1<<(n == 32 ? 31 : (n%32 -1)))));
}
void set_true(int *status, int n)
{
    status[(n-1)/32] |= (1<<(n == 32? 31 : (n%32 - 1))) ;
}
void set_false(int *status, int n)
{
    status[(n-1)/32] &= (~(1<<(n == 32 ? 31 : (n%32 - 1))));
}
#define NSTATION 53
struct station
{
    int arrive_time,degree;
    int connect[2];
    int current;
    struct station *pre,*pconnect[NSTATION + 1];
} station[NSTATION + 1];

int final_route[7000][2];
int num_route = 0;
void get_route(int *status, struct station *start, struct station *end,int limit)
{
    int status_list[7000][2] = {{0},{0}},*ps = &status_list[1][0];
    int sta;
    int realtime = 0;
    struct station *current_station = NULL;
    set_true(status,1);
    *ps = 1;
    for(current_station = start; !(start->current == start->degree && *ps == 1 && *(ps + 1) == 0) ;)
    {
        if(current_station->pconnect[current_station->current] == NULL)
        {
            current_station->current = 0;
            current_station = current_station->pre;
            realtime--;
            memset(ps,0,2 * sizeof(int));
            ps -= 2;
            memcpy(status,ps,2 * sizeof(int));
            continue;
        }
        sta = current_station->pconnect[current_station->current] - &station[0];
        if(!check(status,sta) && current_station->current < current_station->degree)
        {
            current_station->pconnect[current_station->current]->pre = current_station;
            set_true(status, sta);
            ps += 2;
            memcpy(ps,status,2 * sizeof(int));
            current_station = current_station->pconnect[current_station->current];
            realtime++;
            current_station->pre->current++;
            if(current_station == end && realtime <= limit)
            {
                final_route[num_route][0] = status[0];
                final_route[num_route][1] = status[1];
                num_route++;
                current_station = current_station->pre;
                realtime--;
                memset(ps,0,2 * sizeof(int));
                ps -= 2;
                memcpy(status,ps,2 * sizeof(int));
            }
            if(realtime == limit && current_station != end)
            {
                current_station = current_station->pre;
                memset(ps,0,2 * sizeof(int));
                ps -= 2;
                memcpy(status,ps, 2 * sizeof(int));
                realtime--;
            }
        }
        else
        {
            current_station->current++;
        }
    }
}
#define ROUTE 7000
#define TRUE 1
int stat_and_del(int *routes,int end_bit)
{
    int stations[NSTATION + 1] = {0};
    int stat;
    int route_detail[ROUTE][NSTATION + 1] = {{0},{0}}; /* if route[route][0] = -1,means this route had been destoryed*/
    int *route1 = routes;
    int max_value,max_station,find_max,route_left,del,result = 0;
    for(route_left = 0 ; *routes || *(routes + 1); routes += 2,route_left++)
        for(stat = 2; stat < end_bit ; stat++)
            if(check(routes,stat))
            {
                route_detail[route_left][stat] = 1;
            }
    do
    {
        memset(stations,0,(end_bit + 1) * sizeof(int));
        for(routes = route1; *routes || *(routes + 1) ; routes +=2 )
        {
            if(route_detail[(routes - route1 + 2)/2 - 1][0] == -1)
                continue;
            for(stat = 2 ; stat < end_bit ; stat++)
                if(check(routes,stat))
                {
                    stations[stat]++;
                }
        }
        for(find_max = 2,max_value = 0,max_station = 0 ; find_max < end_bit ; find_max++)
        {
            if(stations[find_max] > max_value)
            {
                max_value = stations[find_max];
                max_station = find_max;
            }
        }
        /* we begin to destory! */
        /*printf("NOW we destory station #%d\n",max_station);*/
        for(del = 0,result++,route_left -= max_value ; max_value && route_left; del++)
        {
            if(route_detail[del][0] != -1 && route_detail[del][max_station])
            {
                max_value--;
                route_detail[del][0] = -1;
            }
        }
    }
    while(route_left);
    return result;
}
int main()
{
    int n,m,k,inti,n_cpy = (NSTATION + 1);
    int from,to,outs;
    int route[2] = {0};
    struct station *current_station = NULL;
    short que[10000] = {0};
    short *pHead,*pTail;
    int questatus[2] = {0};
    while(1)
    {
        route[0] = 0;
        route[1] = 0;
        while(num_route >= 0)
        {
            final_route[num_route][0] = 0;
            final_route[num_route][1] = 0;
            num_route--;
        }
        num_route = 0;
        scanf("%d %d %d*c",&n,&m,&k);
        if(n == m && n == k && n== 0)
            break;
        else if(n == 1)
        {
            while(m--)
                scanf("%d %d*c",&from,&to);
            printf("0\n");
        }
        else
        {
            memset(&station[0],0,sizeof(struct station) * (n_cpy));
            memset(que,0,10000 * sizeof(short));
            questatus[0] = 0;
            questatus[1] = 0;
            num_route = 0;
            n_cpy = n;
            for(inti = 2; inti <= n ; inti++)
                station[inti].arrive_time = DIS_UNDEF;
            while(m--)
            {
                scanf("%d %d*c",&from,&to);
                if(!check(station[from].connect,to))
                {
                    set_true(station[from].connect,to);
                    set_true(station[to].connect,from);
                    station[from].pconnect[station[from].degree] = &station[to];
                    station[to].pconnect[station[to].degree] = &station[from];
                    station[from].degree++;
                    station[to].degree++;
                }
            }
            for(pHead = pTail = que - 1,current_station = &station[1],outs = 0 ; n != 0 && pTail <= pHead ; n--)
            {
                for(outs = 0; outs < current_station->degree && current_station->arrive_time < k ; outs++)
                {
                    *(++pHead) = current_station->pconnect[outs] - &station[0];
                    if(station[*pHead].arrive_time == DIS_UNDEF
                            || station[*pHead].arrive_time > current_station->arrive_time + 1
                            || current_station == &station[1])
                        station[*pHead].arrive_time = current_station->arrive_time + 1;
                }
                while(1)
                {
                    pTail++;
                    if(!check(questatus,*pTail))
                    {
                        current_station = &station[*pTail];
                        set_true(questatus,*pTail);
                        break;
                    }
                    if(pTail > pHead)
                        break;
                }
            }
            if(station[n_cpy].arrive_time == DIS_UNDEF)
                printf("0\n");
            else
            {
                get_route(route,&station[1],&station[inti - 1],k); /* inti became (n + 1) in LINE 57 */
                printf("%d\n",stat_and_del(&(final_route[0][0]),inti - 1));
            }
        }
    }
    return 0;
}

提交的结果是内存非法访问，大家帮看看是哪里出问题了-.-
最好附上相应数据.

20 个解决方案

#1

1 3
3 4
4 5
1 2
2 5
1 4
1 4
5 2
6 7 3
1 2
2 3
2 4
2 5
3 6
4 6
5 6
7 9 4
1 3
3 2
2 4
2 5
2 6
4 7
7 5
6 7
7 3
4 4 2
1 2
2 3
3 4
4 2
9 15 4
2 3
1 2
1 3
2 7
1 4
3 4
3 6
7 5
7 6
5 9
6 8
8 9
8 4
4 9
1 7
5 6 3
1 2
2 3
1 3
4 3
5 4
5 2
5 6 100
1 2
2 3
1 3
3 4
4 5
2 5
5 6 2
1 2
1 3
1 4
2 5
3 5
4 5
5 6 1
1 2
1 3
1 4
2 5
3 5
4 5
5 7 2
1 3
3 4
4 5
1 2
2 5
1 4
4 5
50 8 4
1 2
2 39
39 40
40 50
1 40
39 41
41 50
50 41
4 7 2
1 2
1 3
2 3
3 2
3 4
2 4
4 2
这些是我已经测试过的数据。。

#2

come on! somebody help!

#3

好长的代码  而且没有注释


你可以自己多造一些数据 在vs2005上跑

有非法内存使用时会触发断点的

#4

手机上网不便看代码。友情支持
这个有点类似游戏寻路算法，参考A*算法

#5

可是我试验了好多数据。。
还是一样..没有找到哪里出的问题

#6

现在不是算法的问题
是这里有个 数组越界/空指针/等 非法访问内存的问题
可是我找不出..

#7

我在VS2005运行样例时就出现栈检查出错，于是我就把函数内部的数组定义移到外面，避免了栈检查出错。
程序中下标运算很多，而且没有检查。因此我在程序中加了检查下标的assert语句。在运行以下第2组输入时，在函数set_true发现n为0，使下标为-1，assert报错。

输入：
5 6 3
1 2
2 3
1 3
4 3
5 4
5 2
5 6 3
1 2
2 3
1 3
4 3
5 4
5 2
0 0 0

如果不加assert，第2个输出为0，这是错的。建议LZ仔细检查下标处理。以下是加assert的程序：

#include <stdio.h>
#include <memory.h>
#include <assert.h>
#define DIS_UNDEF 99999
int check(int *status, int n)
{
    return (status[(n-1)/32] == (status[(n-1)/32] | (1<<(n == 32 ? 31 : (n%32 -1)))));
}
void set_true(int *status, int n)
{
assert(status!=NULL && n>0);
    status[(n-1)/32] |= (1<<(n == 32? 31 : (n%32 - 1))) ;
}
void set_false(int *status, int n)
{
assert(status!=NULL && n>0);
    status[(n-1)/32] &= (~(1<<(n == 32 ? 31 : (n%32 - 1))));
}
#define NSTATION 53
struct _station
{
    int arrive_time,degree;
    int connect[2];
    int current;
    struct _station *pre,*pconnect[NSTATION + 1];
} station[NSTATION + 1];

int final_route[7000][2];
int num_route = 0;
int status_list[7000][2];
void get_route(int *status, struct _station *start, struct _station *end,int limit)
{
    int *ps = &status_list[1][0];
    int sta;
    int realtime = 0;
    struct _station *current_station = NULL;

    memset(status_list, 0, sizeof(status_list));
    set_true(status,1);
    *ps = 1;
    for(current_station = start; !(start->current == start->degree && *ps == 1 && *(ps + 1) == 0) ;)
    {
assert(current_station!=NULL);
assert(current_station->current>=0 && current_station->current <= NSTATION);
        if(current_station->pconnect[current_station->current] == NULL)
        {
            current_station->current = 0;
            current_station = current_station->pre;
            realtime--;
            memset(ps,0,2 * sizeof(int));
            ps -= 2;
assert(ps>=&status_list[0][0]);
            memcpy(status,ps,2 * sizeof(int));
            continue;
        }
        sta = current_station->pconnect[current_station->current] - &station[0];
        if(!check(status,sta) && current_station->current < current_station->degree)
        {
            current_station->pconnect[current_station->current]->pre = current_station;
            set_true(status, sta);
            ps += 2;
assert(ps<&status_list[7000][0]);
            memcpy(ps,status,2 * sizeof(int));
            current_station = current_station->pconnect[current_station->current];
assert(current_station>=&station[0] && current_station<=&station[NSTATION]);
            realtime++;
            current_station->pre->current++;
            if(current_station == end && realtime <= limit)
            {
assert(num_route>=0 && num_route<7000);
                final_route[num_route][0] = status[0];
                final_route[num_route][1] = status[1];
                num_route++;
                current_station = current_station->pre;
                realtime--;
                memset(ps,0,2 * sizeof(int));
                ps -= 2;
assert(ps<&status_list[7000][0]);
                memcpy(status,ps,2 * sizeof(int));
            }
            if(realtime == limit && current_station != end)
            {
                current_station = current_station->pre;
                memset(ps,0,2 * sizeof(int));
                ps -= 2;
assert(ps<&status_list[7000][0]);
                memcpy(status,ps, 2 * sizeof(int));
                realtime--;
            }
        }
        else
        {
            current_station->current++;
        }
    }
}
#define ROUTE 7000
#define TRUE 1
int stations[NSTATION + 1] = {0};
int route_detail[ROUTE][NSTATION + 1]; /* if route[route][0] = -1,means this route had been destoryed*/
int stat_and_del(int *routes,int end_bit)
{
    int stat;
    int *route1 = routes;
    int max_value,max_station,find_max,route_left,del,result = 0;

    memset(stations, 0, sizeof(stations));
    memset(route_detail, 0, sizeof(stations));
    for(route_left = 0 ; *routes || *(routes + 1); routes += 2,route_left++)
        for(stat = 2; stat < end_bit ; stat++)
            if(check(routes,stat))
            {
assert(route_left>=0 && route_left<ROUTE);
assert(stat>=0 && stat<=NSTATION);
                route_detail[route_left][stat] = 1;
            }
    do
    {
assert((end_bit + 1)<=(NSTATION+1));
        memset(stations,0,(end_bit + 1) * sizeof(int));
        for(routes = route1; *routes || *(routes + 1) ; routes +=2 )
        {
assert(((routes - route1 + 2)/2 - 1)>=0);
assert(((routes - route1 + 2)/2 - 1)<ROUTE);
            if(route_detail[(routes - route1 + 2)/2 - 1][0] == -1)
                continue;
            for(stat = 2 ; stat < end_bit ; stat++)
                if(check(routes,stat))
                {
                    stations[stat]++;
                }
        }
        for(find_max = 2,max_value = 0,max_station = 0 ; find_max < end_bit ; find_max++)
        {
assert(find_max<=NSTATION);
            if(stations[find_max] > max_value)
            {
                max_value = stations[find_max];
                max_station = find_max;
            }
        }
        /* we begin to destory! */
        /*printf("NOW we destory station #%d\n",max_station);*/
        for(del = 0,result++,route_left -= max_value ; max_value && route_left; del++)
        {
assert(del<ROUTE);
            if(route_detail[del][0] != -1 && route_detail[del][max_station])
            {
                max_value--;
                route_detail[del][0] = -1;
            }
        }
    }
    while(route_left);
    return result;
}
int main()
{
    int n,m,k,inti,n_cpy = (NSTATION + 1);
    int from,to,outs;
    int route[2] = {0};
    struct _station *current_station = NULL;
    short que[10000] = {0};
    short *pHead,*pTail;
    int questatus[2] = {0};
    while(1)
    {
        route[0] = 0;
        route[1] = 0;
        while(num_route >= 0)
        {
            final_route[num_route][0] = 0;
            final_route[num_route][1] = 0;
            num_route--;
        }
        num_route = 0;
        scanf("%d %d %d*c",&n,&m,&k);
        if(n == m && n == k && n== 0)
            break;
        else if(n == 1)
        {
            while(m--)
                scanf("%d %d*c",&from,&to);
            printf("0\n");
        }
        else
        {
            memset(&station[0],0,sizeof(struct _station) * (n_cpy));
            memset(que,0,10000 * sizeof(short));
            questatus[0] = 0;
            questatus[1] = 0;
            num_route = 0;
            n_cpy = n;
            for(inti = 2; inti <= n ; inti++)
                station[inti].arrive_time = DIS_UNDEF;
            while(m--)
            {
                scanf("%d %d*c",&from,&to);
                if(!check(station[from].connect,to))
                {
                    set_true(station[from].connect,to);
                    set_true(station[to].connect,from);
                    station[from].pconnect[station[from].degree] = &station[to];
                    station[to].pconnect[station[to].degree] = &station[from];
                    station[from].degree++;
                    station[to].degree++;
                }
            }
            for(pHead = pTail = que - 1,current_station = &station[1],outs = 0 ; n != 0 && pTail <= pHead ; n--)
            {
                for(outs = 0; outs < current_station->degree && current_station->arrive_time < k ; outs++)
                {
assert(outs<=NSTATION);
                    *(++pHead) = current_station->pconnect[outs] - &station[0];
assert((*pHead)>=0 && (*pHead)<=NSTATION);
                    if(station[*pHead].arrive_time == DIS_UNDEF
                            || station[*pHead].arrive_time > current_station->arrive_time + 1
                            || current_station == &station[1])
                        station[*pHead].arrive_time = current_station->arrive_time + 1;
                }
                while(1)
                {
                    pTail++;
                    if(!check(questatus,*pTail))
                    {
assert((*pTail)>=0 && (*pTail)<=NSTATION);
                        current_station = &station[*pTail];
                        set_true(questatus,*pTail);
                        break;
                    }
                    if(pTail > pHead)
                        break;
                }
            }
assert(n_cpy>=0 && n_cpy<=NSTATION);
            if(station[n_cpy].arrive_time == DIS_UNDEF)
                printf("0\n");
            else
            {
assert((inti - 1)>=0 && (inti - 1)<=NSTATION);
                get_route(route,&station[1],&station[inti - 1],k); /* inti became (n + 1) in LINE 57 */
                printf("%d\n",stat_and_del(&(final_route[0][0]),inti - 1));
            }
        }
    }
    return 0;
}

#8

上面有一句说错了：

如果不加assert，第2个输出为0，这是错的。

输出0是对的，而第一次输出2是错的。

#9

我看不懂题意，可以说说么？在ACM给的测试数据中，有那个方案可以使军队在3 minutes 内到达第7个巴士站啊？1-2，1-3，3-4，4-5，1-4，2-5，4-5。那第6和第7个巴士站怎么去？又怎么会有两个4-5出现？

#10

不好意思看错题目，现在完全明白

#11

引用 8 楼 logiciel 的回复:

上面有一句说错了：

如果不加assert，第2个输出为0，这是错的。

输出0是对的，而第一次输出2是错的。

set_true本来就不该会有N == 1的。

#12

还有，这里原来有个初始化的问题我没有弄好，memset(&station[0],0,sizeof(struct station) * (n_cpy));
是错的 正确的该是
memset(&station[1],0,sizeof(struct station) * (n_cpy));
因为原来发的第一个MEMSET对最后一个STATION没有清零。
传上修改后的代码

#include <stdio.h>
#include <memory.h>
#define DIS_UNDEF 99999
int check(int *status, int n)
{
    return (status[(n-1)/32] == (status[(n-1)/32] | (1<<(n == 32 ? 31 : (n%32 -1)))));
}
void set_true(int *status, int n)
{
    status[(n-1)/32] |= (1<<(n == 32? 31 : (n%32 - 1))) ;
}
void set_false(int *status, int n)
{
    status[(n-1)/32] &= (~(1<<(n == 32 ? 31 : (n%32 - 1))));
}
#define NSTATION 53
struct station
{
    int arrive_time,degree;
    int connect[2];
    int current;
    struct station *pre,*pconnect[NSTATION + 1];
} station[NSTATION + 1];

int final_route[7000][2];
int num_route = 0;
void get_route(int *status, struct station *start, struct station *end,int limit)
{
    int status_list[7000][2] = {{0},{0}},*ps = &status_list[1][0];
    int sta;
    int realtime = 0;
    struct station *current_station = NULL;
    set_true(status,1);
    *ps = 1;
    for(current_station = start; !(start->current == start->degree && *ps == 1 && *(ps + 1) == 0) ;)
    {
        if(current_station->pconnect[current_station->current] == NULL)
        {
            current_station->current = 0;
            current_station = current_station->pre;
            realtime--;
            memset(ps,0,2 * sizeof(int));
            ps -= 2;
            memcpy(status,ps,2 * sizeof(int));
            continue;
        }
        sta = current_station->pconnect[current_station->current] - &station[0];
        if(!check(status,sta) && current_station->current < current_station->degree)
        {
            current_station->pconnect[current_station->current]->pre = current_station;
            set_true(status, sta);
            ps += 2;
            memcpy(ps,status,2 * sizeof(int));
            current_station = current_station->pconnect[current_station->current];
            realtime++;
            current_station->pre->current++;
            if(current_station == end && realtime <= limit)
            {
                final_route[num_route][0] = status[0];
                final_route[num_route][1] = status[1];
                num_route++;
                current_station = current_station->pre;
                realtime--;
                memset(ps,0,2 * sizeof(int));
                ps -= 2;
                memcpy(status,ps,2 * sizeof(int));
            }
            if(realtime == limit && current_station != end)
            {
                current_station = current_station->pre;
                memset(ps,0,2 * sizeof(int));
                ps -= 2;
                memcpy(status,ps, 2 * sizeof(int));
                realtime--;
            }
        }
        else
        {
            current_station->current++;
        }
    }
}
#define ROUTE 7000
#define TRUE 1
int stat_and_del(int *routes,int end_bit)
{
    int stations[NSTATION + 1] = {0};
    int stat;
    int route_detail[ROUTE][NSTATION + 1] = {{0},{0}}; /* if route[route][0] = -1,means this route had been destoryed*/
    int *route1 = routes;
    int max_value,max_station,find_max,route_left,del,result = 0;
    for(route_left = 0 ; *routes || *(routes + 1); routes += 2,route_left++)
        for(stat = 2; stat < end_bit ; stat++)
            if(check(routes,stat))
            {
                route_detail[route_left][stat] = 1;
            }
    do
    {
        memset(stations,0,(end_bit + 1) * sizeof(int));
        for(routes = route1; *routes || *(routes + 1) ; routes +=2 )
        {
            if(route_detail[(routes - route1 + 2)/2 - 1][0] == -1)
                continue;
            for(stat = 2 ; stat < end_bit ; stat++)
                if(check(routes,stat))
                {
                    stations[stat]++;
                }
        }
        for(find_max = 2,max_value = 0,max_station = 0 ; find_max < end_bit ; find_max++)
        {
            if(stations[find_max] > max_value)
            {
                max_value = stations[find_max];
                max_station = find_max;
            }
        }
        /* we begin to destory! */
        printf("NOW we destory station #%d\n",max_station);
        for(del = 0,result++,route_left -= max_value ; max_value && route_left; del++)
        {
            if(route_detail[del][0] != -1 && route_detail[del][max_station])
            {
                max_value--;
                route_detail[del][0] = -1;
            }
        }
    }
    while(route_left);
    return result;
}
int main()
{
    int n,m,k,inti,n_cpy = (NSTATION + 1);
    int from,to,outs;
    int route[2] = {0};
    struct station *current_station = NULL;
    short que[10000] = {0};
    short *pHead,*pTail;
    int questatus[2] = {0};
    while(1)
    {
        route[0] = 0;
        route[1] = 0;
        while(num_route >= 0)
        {
            final_route[num_route][0] = 0;
            final_route[num_route][1] = 0;
            num_route--;
        }
        num_route = 0;
        scanf("%d %d %d*c",&n,&m,&k);
        if(n == m && n == k && n== 0)
            break;
        else if(n == 1)
        {
            while(m--)
                scanf("%d %d*c",&from,&to);
            printf("0\n");
        }
        else
        {
            memset(&station[1],0,sizeof(struct station) * (n_cpy));
            memset(que,0,10000 * sizeof(short));
            questatus[0] = 0;
            questatus[1] = 0;
            num_route = 0;
            n_cpy = n;
            for(inti = 2; inti <= n ; inti++)
                station[inti].arrive_time = DIS_UNDEF;
            while(m--)
            {
                scanf("%d %d*c",&from,&to);
                if(!check(station[from].connect,to))
                {
                    set_true(station[from].connect,to);
                    set_true(station[to].connect,from);
                    station[from].pconnect[station[from].degree] = &station[to];
                    station[to].pconnect[station[to].degree] = &station[from];
                    station[from].degree++;
                    station[to].degree++;
                }
            }
            for(pHead = pTail = que - 1,current_station = &station[1],outs = 0 ; n != 0 && pTail <= pHead ; n--)
            {
                for(outs = 0; outs < current_station->degree && current_station->arrive_time < k ; outs++)
                {
                    *(++pHead) = current_station->pconnect[outs] - &station[0];
                    if(station[*pHead].arrive_time == DIS_UNDEF
                            || station[*pHead].arrive_time > current_station->arrive_time + 1
                            || current_station == &station[1])
                        station[*pHead].arrive_time = current_station->arrive_time + 1;
                }
                while(1)
                {
                    pTail++;
                    if(!check(questatus,*pTail))
                    {
                        current_station = &station[*pTail];
                        set_true(questatus,*pTail);
                        break;
                    }
                    if(pTail > pHead)
                        break;
                }
            }
            if(station[n_cpy].arrive_time == DIS_UNDEF)
                printf("0\n");
            else
            {
                get_route(route,&station[1],&station[inti - 1],k); /* inti became (n + 1) in LINE 57 */
                printf("%d\n",stat_and_del(&(final_route[0][0]),inti - 1));
            }
        }
    }
    return 0;
}

#13

修改过之后
5 6 3
1 2
2 3
1 3
4 3
5 4
5 2
5 6 3
1 2
2 3
1 3
4 3
5 4
5 2
的结果为
2
2；
消灭的是2，3 STATIONS;
还有 怎么能得到N == 1的？

#14

LZ可试以下输入：
2 1 2
1 2

程序陷入死循环。

#15

上面输入不符合题意。但其他AC的程序不会陷入死循环。

#16

LZ可用以下程序设置输入的上限来测试程序：

        num_route = 0;
        //修改scanf("%d %d %d*c",&n,&m,&k);
        n=50; k=999; //新加
        if(n == m && n == k && n== 0)
            break;
        else if(n == 1)
        {
            while(m--)
                scanf("%d %d*c",&from,&to);
            printf("0\n");
        }
        else
        {
            memset(&station[1],0,sizeof(struct station) * (n_cpy));
            memset(que,0,10000 * sizeof(short));
            questatus[0] = 0;
            questatus[1] = 0;
            num_route = 0;
            n_cpy = n;
            for(inti = 2; inti <= n ; inti++)
                station[inti].arrive_time = DIS_UNDEF;

            //while(m--)
            m=0;//新加
            for(from=1; from<n;from++)for(to=1; to<=n; to++)//新加
            {
                if (from == to) continue;//新加
                m++;//scanf("%d %d*c",&from,&to);
                printf("m=%d from=%d to=%d\n", m, from, to);//新加
                if(!check(station[from].connect,to))
                {

我试了一下，程序出现内存非法访问。

#17

引用 16 楼 logiciel 的回复:

LZ可用以下程序设置输入的上限来测试程序：

C/C++ code
        num_route = 0;
        //修改scanf("%d %d %d*c",&n,&m,&k);
        n=50; k=999; //新加
        if(n == m && n == k && n== 0)
     ……

我也看到这个 错误了
现在调试看看，好似找不出哪里有问题，BTW把 INT ARRAY[2]都改成unsigned了

#18

找到问题了。。
  current_station->pconnect[current_station->current]->pre = current_station;
这里
current_station->current
竟然等于 -1..
OMFG!

#19

current_station->current
怎么会等于-1?!

#20

算法寫得好複雜啊。

#21

• Linux环境定位C程序内存泄露以及非法访问的方法