fork(1) download
copy 
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<string.h>
  4. #include<sstream>
  5. #define max 11000
  6. #define infinity 999999
  7. int arr[max][20];
  8. int state[max];
  9. int pred[max];
  10. int n;
  11. int colour[max];
  12. using namespace std;
  13. void reset_dp()
  14. {
  15. 	for(int i=0;i<=n;i++)
  16. 	{
  17. 		for(int j=0;j<=20;j++)
  18. 		{
  19. 			arr[i][j]=-1;
  20. 		}
  21. 	}
  22. }
  23. void reset_pred()
  24. {
  25. 	for(int i=0;i<n;i++)
  26. 	{
  27. 		pred[i]=-1;
  28. 	}
  29. }
  30. int fun(int vi,int c)
  31. {
  32. 	int m,flag,k;
  33. 	if(arr[vi][c]!=-1)
  34. 	{
  35. 		return arr[vi][c];
  36. 	}
  37. 	flag=k=0;
  38. 	for(int i=0;i<n;i++)
  39. 	{
  40. 		if(pred[i]==vi)
  41. 		{
  42. 			flag=1;
  43. 			m=infinity;
  44. 			for(int cl=1;cl<=20;cl++)
  45. 			{
  46. 				if(cl!=c)
  47. 				{
  48. 					arr[i][cl]=fun(i,cl);
  49. 					if(arr[i][cl]<m)
  50. 					{
  51. 						m=arr[i][cl];
  52. 					}
  53. 				}
  54. 			}
  55. 		  k=k+m;
  56. 		}
  57. 	}
  58. 	if(flag==0)
  59. 	{
  60. 		return c;
  61. 	}
  62. 	else
  63. 	{
  64. 		arr[vi][c]=c+k;
  65. 		return arr[vi][c];
  66. 	}
  67. }
  68.  
  69. int main()
  70. { 
  71.     int k,vi,min;
  72.     while(1)
  73.     {
  74.     	cin>>n;
  75.     	if(n==0)
  76.     	  break;
  77.     	reset_dp();
  78.     	min=infinity;
  79.     	reset_pred();
  80.     	k=getchar();
  81.     	for(int i=0;i<n;i++)
  82.          {
  83.             string str;
  84.             stringstream ss;
  85.             getline(cin,str);
  86.             ss<<str;
  87.             char c;
  88.             int u, v;
  89.             ss>>u;
  90.             ss>>c;
  91.             while(ss>>v)
  92.             {
  93.                 pred[v]=u;
  94.             }
  95.         }
  96.         for(int i=0;i<n;i++)
  97.           {
  98.     	    if(pred[i]==-1)
  99.     	      {
  100.     		     vi=i;
  101.     		      break;
  102.     	     }
  103.           }
  104.         for(int i=1;i<=20;i++)
  105.         {
  106.         	int k=fun(vi,i);
  107.         	if(k<min)
  108.         	  min=k;
  109.         }
  110.  
  111.         cout<<min<<"\n";
  112.     }
  113.     return 0;
  114. }
  115.  
  116.  
Success #stdin #stdout 0s 4424KB
comments (?)
stdin
copy 
7
0: 1 5 6
1: 2
2: 3 4
5:
6:
3:
4:

10
0:
2: 1 4 5
1: 6 7 8
6:
7:
8: 0 3 9
5:
4:
3:
9:

0
stdout
copy 
9
14
https://ideone.com/xHJ0FI
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

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!