fork download
copy 
  1. #include<stdio.h>
  2. #include<iostream>
  3. using namespace std;
  4.  
  5. int main ()
  6. {
  7. /*#ifndef ONLINE_JUDGE
  8.   freopen("input.txt", "r", stdin);
  9. #endif*/
  10.   int d;
  11.   long i, j, k, n, m, x, y, s, st, f;
  12.   long long unsigned int p, day;
  13.   scanf("%ld", &n);
  14.   long adj[n][n], mat[n][2];
  15.  
  16.   for(i=1; i<=n; i++)
  17.   {
  18.     for(j=1; j<=n; j++)
  19.     {
  20.       adj[i][j]=3122;
  21.     }
  22.   }
  23.   for(i=1; i<=n; i++)
  24.   {
  25.     for(j=1; j<=2; j++)
  26.     {
  27.       mat[i][j]=0;
  28.     }
  29.   }
  30.   for(i=1; i<n; i++)
  31.   {
  32.     scanf("%ld %ld %d", &x, &y, &d);
  33.     adj[x][y]=adj[y][x]=d;
  34.     if(mat[x][1])
  35.       mat[x][2]=y;
  36.     else
  37.       mat[x][1]=y;
  38.     if(mat[y][1])
  39.       mat[y][2]=x;
  40.     else
  41.       mat[y][1]=x;
  42.   }
  43.   scanf("%ld", &m);
  44.   while(m--)
  45.   {
  46. //     long day, st;
  47.     scanf("%ld %ld %llu", &s, &f, &p);
  48.     st=s;
  49.     for(k=1; k<=2; k++)
  50.     {
  51.       i=k;
  52.       int flag=0;
  53.       long c[n], travelled=0, dist=0;
  54.       day=1;
  55.       for(j=1; j<=n; j++)
  56. 	c[j]=0;
  57.       while(mat[st][i]!=0)
  58.       {
  59. 	c[st]=1;
  60. 	if(c[mat[st][i]])
  61. 	{
  62. 	  if(i==1)
  63. 	    i=2;
  64. 	  else
  65. 	    i=1;
  66. 	}
  67. 	travelled+=adj[st][mat[st][i]];
  68. 	if(travelled<=p)
  69. 	{
  70. 	  dist+=adj[st][mat[st][i]];
  71. 	  st=mat[st][i];
  72. 	}      
  73. 	else
  74. 	{
  75. 	  travelled=0;
  76. 	  day++;
  77. 	}
  78. 	if(mat[st][i]==0)
  79. 	{
  80.  
  81. 	  st=s;
  82. 	  break;
  83. 	}
  84. 	if(mat[st][i]==f)
  85. 	{
  86. 	  travelled+=adj[st][mat[st][i]];
  87. 	  if(travelled>p)
  88. 	    day++;
  89. 	  flag=1;
  90. 	  break;
  91. 	}
  92. 	i=1;
  93.       }
  94.       if(flag)
  95.       {
  96. 	break;
  97.       }
  98.     }
  99.     printf("%llu\n", day);
  100.   }
  101.   return 0;
  102. }
Success #stdin #stdout 0s 3300KB
comments (?)
stdin
copy 
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
stdout
copy 
1
2
1
1
1
https://ideone.com/a3hF8j
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!