c - Codechef十月挑战 child 旅行的错误答案？

Question

Closed. This question is off-topic。它当前不接受答案。
                            
                        
                    
                
                            
                                
                
                        
                            
                        
                    
                        
                            想改善这个问题吗？ Update the question，所以它是 on-topic，用于堆栈溢出。
                        
                        5年前关闭。
                                                                                            
                
        
这是比赛的问题陈述： http://www.codechef.com/OCT14/problems/TRIPS
附注：我看过社论，但想知道我的解决方案出了什么问题。
Bytelandian学校之间有一种新趋势。 “ Byteland旅游局”为高中生开发了一个新项目。该项目就是所谓的“儿童之旅”。
该项目本身非常简单：在Byteland中有一些旅游路线，还有N个旅游园区（从1到N）。为了经济起见，它们之间确实有N-1条路。当然，即使有这个建议，也有可能从任何旅游校园到任何其他校园。此外，为了安全起见，每条道路不超过2公里。
当某些学生想旅行时，他首先选择了他的出发校园-他被直升飞机送到（比如说）那里。他还选择了自己的最终目的地校园。从他的最终目的地，他将再次被（例如）直升机运送到他的家中。这样学生就不会步行额外的距离。选择起点和终点并放出瞳孔后，他将沿着唯一的路线开始运动。没有一个学生会无限强壮，因此，该学生首先看了旅游路线图，然后选择了当天可以到达的最远的校园（根据安全规定，严禁不睡觉在校园里，因为狼人可能会有一点麻烦，然后搬到那里。然后新的一天开始，并重复直到到达目的地的那一刻。
当然，并不是所有的学生都平等。有人数学很好，有人英语，有人在体育。因此，所有高中生都有不同的优势是很自然的。
我们称力量为学生一天可以通过的最大公里数。现在，孩子们收到了很多询问。对于每个查询，都将为您提供起点，终点和实力。要求您计算每次旅行的天数。校园地图及其之间的距离也将提供给您。
输入值
输入的第一行包含整数N，表示校园数。
接下来的N-1条线包含形式为X Y D的三元组，这意味着在第X个和第Y个校园之间有一条道路，长度为D公里。
然后有一行带有单个整数M的行，表示查询的数量。
然后，有M条线的三联形式为S F P，这意味着旅行从校园S开始，在校园F结束，并且学生具有P的强度。
输出量
对于每个查询，请在单独的行中输出天数。
约束条件
1≤N，M≤100000
1≤X，Y，S，F≤N
1≤D≤2
2≤P≤2 * N
例
输入：
5
1 2 1
2 3 2
1 4 2
4 5 1
5
1 5 3
1 3 2
2 5 4
1 2 10
4 5 2
输出：
1个
2
1个
1个
1个


我使用的逻辑：
由于边的数量是n-1和n个总顶点，因此将有n-2个具有2度的顶点和2个具有1度的顶点（这将是两个端点）。我所做的是我创建了4个大小数组n，其中两个将存储该顶点下一个顶点的值，另外两个将在该顶点的边缘上存储权重。现在，我将发现起点和终点的顶点，因为使用输入它们仅具有度1。一旦我到达起点，我将遍历它到存储下一个顶点和边的权重的终点的唯一路径。现在，每当我得到查询时，我便简单地将顺序路径存储在数组中，现在我就遍历数组了，得到我的结果。
我的代码：

#include<stdio.h>
int main()
{   
    int n;
    scanf("%d",&n);
    int a[n],weighta[n],b[n],weightb[n],i,j,k,x,y,d,count,previousj;
    //initialize
    for (i = 0; i < n; ++i)
    {
        a[i]=-1;b[i]=-1;weighta[i]=-1,weightb[i]=-1;
    }
    for(i=0;i<n-1;i++)
    {
        scanf("%d%d%d",&x,&y,&d);
        if(a[x-1]==-1)
        {
            a[x-1]=y-1;
            weighta[x-1]=d;
        }
        else
        {   
            b[x-1]=y-1;
            weightb[x-1]=d;
        }   
        if(a[y-1]==-1)
        {   
            a[y-1]=x-1;
            weighta[y-1]=d;
        }
        else
        {   
            b[y-1]=x-1;
            weightb[y-1]=d;
        }
    }
    /*for (i = 0; i < n; ++i)
    {
        printf("a[i] %d weighta[i] %d b[i]%d  weightb[i] %d\n",a[i],weighta[i],b[i],weightb[i]);
    }*/
    for(i=0;i<n;i++)
    {
        if(b[i]==-1)
            break;
    }
    //printf("first end %d %d\n",i,a[i] ); 
    int finalval[n],finalweight[n];
    for (k = 0; k < n; ++k)
    {
        finalval[k]=0;finalweight[k]=0;
    }
    j=i;count=0;
    finalval[count]=j;
    finalweight[count]=weighta[j];
    previousj=j;
    j=a[j];
    //printf("count %d finalval %d finalweight %d\n",count,finalval[count],finalweight[count] );
    count++;
    //printf("%s\n","HI" );
    while(b[j]!=-1)
    {        //printf("%d\n",b[j] );
        //finalval[count]=j;
        //finalweight[count]=weighta[j];
        if(a[j]!=previousj)
        {
            finalval[count]=j;
            finalweight[count]=weighta[j];
            previousj=j;
            j=a[j];
            //printf("count %d finalval %d finalweight %d\n",count,finalval[count],finalweight[count] );
            count++;
        }
        else
        {
            finalval[count]=j;
            finalweight[count]=weightb[j];
            previousj=j;
            j=b[j];
            //("count %d finalval %d finalweight %d\n",count,finalval[count],finalweight[count] );
            count++;
        }   

    }
    finalval[count]=j;
            finalweight[count]=finalweight[count];
            count++;
    /*
    for (i = 0; i < n; ++i)
    {
        printf("final %d %d\n",i,finalval[i] );
    }*/
    int m;
    scanf("%d",&m);
    while(m--)
    {   int s,f,p,flag=0,pos_s,pos_f;
        scanf("%d%d%d",&s,&f,&p);
        s--;f--;
        for (i = 0; i <count; ++i)
        {
            if(finalval[i]==s)
            {
                pos_s=i;
                if(flag==1)
                    break;
                flag=1;
            }
            if(finalval[i]==f)
            {   
                pos_f=i;
                if(flag==1)
                    break;
                flag=1;
            }
        }
        int temp,days;
        //("pos_s %d pos_f %d\n",pos_s,pos_f);
        if(pos_s<pos_f)
        {   //printf("%s\n","hi" );
            temp=p;days=1;
            for(i=pos_s;i<pos_f;i++)
            {
                if(temp>finalweight[i])
                    temp-=finalweight[i];
                else if(temp==finalweight[i])
                {
                    //days++;
                    temp=0;
                }   
                else
                {   
                    days++;
                    temp=p;
                    temp-=finalweight[i];
                }   
            }   
            //if(temp==p)
            //  days--;

        }
        else if(pos_s==pos_f)
            days=1; 
        else
        {   temp=p;days=1;
            for(i=pos_s-1;i>=pos_f;i--)
            {
                if(temp>finalweight[i])
                    temp-=finalweight[i];
                else if(temp==finalweight[i])
                {
                    //days++;
                    temp=0;
                }   
                else
                {   
                    days++;
                    temp=p;
                    temp-=finalweight[i];
                }   
            }   
            //if(temp==p)
            //  days--;

        }
        printf("%d\n",days);        




    }   



    return 0;
} 

最佳答案

接下来的网络呢？

  1
  |
2-3-4

4分3边...

关于c - Codechef十月挑战 child 旅行的错误答案？ ，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26365543/

上一篇：c - 为什么偶数整数的输出无法正常工作

下一篇：c - 了解汇编代码行 andl 65535 %edx

相关文章：

c - 什么循环不变量用于整数对数？

c - 为什么初始化高优先级接收中断的UART需要使RCSTA2bits.CREN = 0;

有人能告诉我我的错误在哪里吗？我的程序给出了错误的输出

java - Dijkstra - 定位上一个 vector

C 段错误 : 11 fgets

c - 将 execv 与 Linux 的任意命令一起使用——echo、date、ls 等

python - 如何交错或创建两个字符串的唯一排列(无递归)

java - 最高 "Valued"回文

c - 比较算法的好方法是什么？

java - 在 Java 中检测 Hashmap 中的循环依赖

Answer 1

接下来的网络呢？

  1
  |
2-3-4

4分3边...