求解，ACM题为什么会WA？该如何解决

求解，ACM题为什么会WA？？
http://acm.fafu.edu.cn/showproblem?problem_id=1081
报销问题

Time Limit:1000MS Memory Limit:65536K
Total Submit:150 Accepted:29

Description

??XX总公司要派小李子去一些分公司了解分公司的运营情况，但是在出发前小李子要先知道目的地与总公司的距离，以便在向公司报销路费时可以有据可依，你的任务就是求出这个距离(输入数据保证每两个公司之间有且只有一条路径可达)。

Input

??第一行一个整数T, 代表T组输入数据，每组数据的第一行有两个整数n m，其中n (0< n <=30000)代表公司的总数(公司的编号从0~n-1，总公司的编号恒为0)，m(0<= m <= n)代表询问的次数;在接下来的n-1行中每行有三个整数a b c，代表公司a到公司b有一条双向可达的路径，距离为c(0 <= c <= 100);最后是m次询问，每次询问有1个整数d，代表你要求的从总公司到分公司d的距离。

Output

??对于每组数据中的每个询问输出一行代表从总公司到询问的分公司的距离。

Sample Input


2
3 2
0 1 1
1 2 2
2
1
4 2
0 1 1
0 2 5
3 2 8
0
3
Sample Output


3
1
0
13

C/C++ code

# include<stdio.h># include<malloc.h># include<string.h>int n,m,d;struct node {    int id,dist;    struct node * next;}a[30001],*p,* q;int vis[30001],length[30001];void dfs(int i){    int u;    vis[i] = 1;    p = a[i].next;    while(p)    {        u = p->id;        if(!length[u])length[u] = length[i]+p->dist;        if(!vis[u]) dfs(u);        if(p == NULL)return;        p = p->next;    }}int main(void){    int t,i,x,y,z;    scanf("%d",&t);    while(t--)    {        memset(length,0,sizeof(length));        memset(vis,0,sizeof(vis));        for(i=0;i<n;i++)            a[i].next = NULL;        scanf("%d%d",&n,&m);        for(i=1;i<n;i++)        {            scanf("%d%d%d",&x,&y,&z);            p = (node *)malloc(sizeof(node));            q = (node *)malloc(sizeof(node));            p->id = y;            p->dist = z;            p->next = a[x].next;            a[x].next = p;            q->id = x;            q->dist = z;            q->next = a[y].next;            a[y].next = q;        }        dfs(0);        for(i=0;i<m;i++)        {            scanf("%d",&d);            printf("%d\n",length[d]);        }    }    return 0;}

[解决办法]
试一下在每个用例输出后增加以下代码：
for(i=0;i<n;i++)
if(a[i].next) free(a[i].next);

[解决办法]
我的也wa了,自己调吧.

C/C++ code

#include <iostream>using namespace std;#define INFINITE 99999999#define MY_MAX 30int G[MY_MAX][MY_MAX];int Dist[MY_MAX];int UsedFlag[MY_MAX];int nUsedNum;int main(){    freopen("in.txt","r",stdin);    int T, N, M;    int i, j;    cin >> T;    while (T--) {        cin >> N;        memset(UsedFlag,0,sizeof(UsedFlag));        for (i = 0; i < MY_MAX; i++) {            Dist[i] = INFINITE;            for (j = 0; j < MY_MAX; j++)                G[i][j] = INFINITE;        }                for (i = 1; i <= N; i++) {            int nNo, p;            cin >> nNo >> p;            G[0][i] = p-1;            Dist[i] = p-1;        }        cin >> M;        for (i = 0; i < M; i++) {            int nNo1, nNo2, p;            cin >> nNo1 >> nNo1 >> p;            G[nNo1][nNo2] = p;            }        for (i = 1; i < N; i++)            for (j = i+1; j <= N; j++)                if (G[0][i] == G[0][j])                    G[i][j] = G[j][i] = 0;        nUsedNum = 1;        UsedFlag[0] = 1;        while (nUsedNum <= N) {            int nMinI,nMinDist = INFINITE;            for (i = 1; i <= N; i++) {                if (Dist[i] < nMinDist && UsedFlag[i] == 0) {                    nMinDist = Dist[i];                    nMinI = i;                }            }            nUsedNum++;            UsedFlag[nMinI] = 1;            for (i = 1; i <= N; i++){                if (UsedFlag[i] == 0 && Dist[i] > Dist[nMinI] + G[nMinI][i])                    Dist[i] = Dist[nMinI] + G[nMinI][i];            }        }                for (i = 1; i <= N; i++)            cout << i << " " << Dist[i] << endl;                int nTotalNum = 0;        for (i = 1; i <= N; ++i) {            bool bFound = false;            for (j = 1; j < N; j++) {                int k;                for (k = j+1; k <= N; k++) {                    if (Dist[i] == Dist[j] + Dist[k] && j != i && k != i && bFound == false){                        nTotalNum++;                        bFound = true;                        break;                    }                }                if (bFound == true)                    break;            }        }        cout << nTotalNum << endl;    }    while (1);    return 0;} 
  

 

查看更多 下一篇