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。一旦我到达起点，我将遍历它到存储下一个顶点和边的权重的终点的唯一路径。现在，每当我得到查询时，我便简单地将顺序路径存储在数组中，现在我就遍历数组了，得到我的结果。
我的代码：
4分3边...
想改善这个问题吗？ 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边...
10-06 14:36