fork(1) download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. #define max 110
  5. int status[max];
  6. #define size 100000
  7. int n,r,s,d,t;
  8. int adj[max][max];
  9. using namespace std;
  10. vector<int> v;
  11. struct st
  12. {
  13. 	int v;
  14. 	int trst;
  15. 	int city[max];
  16. 	st(int vr,int p)
  17. 	{
  18. 		v=vr;
  19. 		trst=p;
  20. 		for(int i=1;i<=n;i++)
  21. 		{
  22. 			city[i]=0;
  23. 		}
  24. 		city[vr]=1;
  25. 	}
  26. };
  27. struct queue
  28. {
  29. 	int front;
  30. 	int rear;
  31. 	st* arr[size];
  32. 	void insert(st*);
  33. 	st* del();
  34. 	queue();
  35. }q;
  36. queue::queue()
  37. {
  38.        front=-1;
  39. 	   rear=-1; 	
  40. }
  41. st* queue::del()
  42. {
  43.  
  44. 	if(front!=-1)
  45. 	{
  46. 		st* f=arr[front];
  47. 		if(front==rear)
  48. 		{
  49. 			front=-1;
  50. 			rear=-1;
  51. 		}
  52. 		else
  53. 		{
  54. 		  front=(front+1)%size;
  55. 	    }
  56. 		return f;
  57.    }
  58.  
  59. }
  60. void queue::insert(st* f)
  61. {
  62. 	   rear=(rear+1)%size;
  63. 	   arr[rear]=f;
  64. 	   if(front==-1)
  65. 	     front=0;	   
  66. }
  67. void reset_adj()
  68. {
  69. 	for(int i=1;i<=n;i++)
  70. 	{
  71. 		for(int j=1;j<=n;j++)
  72. 		{
  73. 			adj[i][j]=-1;
  74. 		}
  75. 	}
  76. }
  77. void set(st* temp,st* s1)
  78. {
  79. 	for(int i=1;i<=n;i++)
  80. 	{
  81. 		if(temp->city[i]==1)
  82. 		{
  83. 			s1->city[i]=1;
  84. 		}
  85. 	}
  86. }
  87. void get_path()
  88. {
  89. 	int p;
  90. 	while(q.front!=-1)
  91. 	{
  92. 		st* temp=q.del();
  93. 		for(int i=1;i<=n;i++)
  94. 		{
  95. 		   if((adj[temp->v][i]>0)&&(temp->city[i]==0))
  96. 		   {
  97.  
  98. 			if(adj[temp->v][i]<temp->trst)
  99. 		   	{
  100. 		   		p=adj[temp->v][i];
  101. 		   	}
  102. 		   	else
  103. 		   	{
  104. 		   		p=temp->trst;
  105. 		   	}
  106. 		   	st* s1=new st(i,p);
  107. 		   	set(temp,s1);
  108. 		   	if(i==t)
  109. 		   	{
  110. 		   		v.push_back(s1->trst);
  111. 		   		for(int i=1;i<=n;i++)
  112. 		   		{
  113. 		   			s1->city[i]=1;
  114. 		   		}
  115. 		   	}
  116. 		   	q.insert(s1);
  117. 		   }	
  118. 		}
  119. 	}
  120. }
  121. int main()
  122. { 
  123.     int v1,v2,wt,m;
  124.     int tst=0;
  125.     while(cin>>n>>r)
  126.     {
  127.     	if((n==0)&&(r==0))
  128.     	   break;
  129.     	reset_adj();
  130.     	tst++;
  131.     	for(int i=1;i<=r;i++)
  132.     	{
  133.     	   cin>>v1>>v2>>wt;
  134. 		   adj[v1][v2]=wt;
  135. 		   adj[v2][v1]=wt;
  136.  
  137.     	}
  138.         cin>>s>>t>>d;
  139.         if(d==0)
  140.         {
  141.         	m=0;
  142.         }
  143.  
  144.         if((s!=t)&&(d!=0))
  145.         {
  146.  
  147.         st* s1=new st(s,d+1);
  148.         q.insert(s1);
  149.         get_path();
  150.         sort(v.begin(),v.end());
  151.         int p=(v.back()-1);
  152.         if(d%p==0)
  153.         {
  154.         	m=d/p;
  155.         }
  156.         else 
  157.         {
  158.         	m=(d/p)+1;
  159.         }
  160. 		}
  161. 		if((s==t)&&(d!=0))
  162. 		{
  163. 			m=1;
  164. 		}
  165.         cout<<"Scenario #"<<tst<<"\n";
  166.         cout<<"Minimum Number of Trips = "<<m<<"\n";
  167.         cout<<"\n";
  168.         v.erase(v.begin(),v.end());
  169.     }
  170.    return 0;
  171. }
  172.  
Success #stdin #stdout 0s 3916KB
comments (?)
stdin
copy 
5 6
2 4 45
1 2 35
1 3 19
2 5 96
3 5 28
2 3 17
1 1 100
5 6
2 4 45
1 2 35
1 3 19
2 5 96
3 5 28
2 3 17
1 5 100
5 7
1 4 10
2 4 45
1 2 35
1 3 19
2 5 96
3 5 28
2 3 17
1 5 100
5 6
2 4 45
1 2 35
1 3 19
2 5 96
3 5 28
2 3 17
5 2 25
0 0
stdout
copy 
Scenario #1
Minimum Number of Trips = 1

Scenario #2
Minimum Number of Trips = 3

Scenario #3
Minimum Number of Trips = 3

Scenario #4
Minimum Number of Trips = 1
https://ideone.com/mlyEL1
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!