fork(10) download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. #define max 110
  5. #define size 10000
  6. std::vector<int> v;
  7. int n,e,s,t,k;
  8. int adj[max][max];
  9. using namespace std;
  10. struct st
  11. {
  12. 	int v;
  13. 	int dist;
  14. };
  15. struct queue
  16. {
  17. 	int front;
  18. 	int rear;
  19. 	st arr[size];
  20. 	void insert(st);
  21. 	st del();
  22. 	queue();
  23. }q;
  24. queue::queue()
  25. {
  26.        front=-1;
  27. 	   rear=-1; 	
  28. }
  29. st queue::del()
  30. {
  31.  
  32. 	if(front!=-1)
  33. 	{
  34. 		st f=arr[front];
  35. 		if(front==rear)
  36. 		{
  37. 			front=-1;
  38. 			rear=-1;
  39. 		}
  40. 		else
  41. 		{
  42. 		  front=(front+1)%size;
  43. 	    }
  44. 		return f;
  45.    }
  46.  
  47. }
  48. void queue::insert(st f)
  49. {
  50. 	   rear=(rear+1)%size;
  51. 	   arr[rear]=f;
  52. 	   if(front==-1)
  53. 	     front=0;	   
  54. }
  55. void reset_adj()
  56. {
  57. 	for(int i=1;i<=n;i++)
  58. 	{
  59. 		for(int j=1;j<=n;j++)
  60. 		{
  61. 			adj[i][j]=-1;
  62. 		}
  63. 	}
  64. }
  65. void make_queue_empty()
  66. {
  67. 	while(q.front!=-1)
  68. 	{
  69. 		st temp=q.del();
  70. 	}
  71. }
  72. void get_k_longest()
  73. {
  74. 	int cnt=0;
  75. 	while(q.front!=-1)
  76. 	{
  77. 		st temp=q.del();
  78. 		for(int i=1;i<=n;i++)
  79. 		{
  80. 		   if(adj[temp.v][i]>=0)
  81. 		   {
  82. 		   	st s1;
  83. 		   	s1.v=i;
  84. 		   	s1.dist=temp.dist+adj[temp.v][i];
  85. 		   	q.insert(s1);
  86. 		   	if(i==t)
  87. 		   	{
  88. 		   		v.push_back(s1.dist);
  89. 		   		cnt++;
  90. 		   		if(cnt>=size)
  91. 		   		   return;
  92. 		   	}
  93. 		   }	
  94. 		}
  95. 	}
  96. }
  97. int main()
  98. { 
  99.     int v1,v2,wt;
  100.     while(1)
  101.     {
  102.     	cin>>n>>e;
  103.     	if((n==0)&&(e==0))
  104.     	   break;
  105.     	reset_adj();
  106.     	cin>>s>>t>>k;
  107.     	for(int i=1;i<=e;i++)
  108.     	{
  109.     	   cin>>v1>>v2>>wt;
  110. 		   adj[v1][v2]=wt;	
  111.     	}
  112.  
  113.     	st s1;
  114.     	s1.v=s;
  115.     	s1.dist=0;
  116.     	q.insert(s1);
  117.     	get_k_longest();
  118.     	sort(v.begin(),v.end());
  119.     	vector <int>::iterator it;
  120.     	int cnt=0;
  121. 		for(it=v.begin();it<v.end();it++)
  122. 		{
  123. 		   	cnt++;
  124. 		   	if(cnt==k)
  125. 		   	{
  126. 		   		cout<<*it<<"\n";
  127. 		   		make_queue_empty();
  128. 		   		v.clear();
  129. 		   		break;
  130. 		   	}
  131. 		} 
  132. 		if(cnt<k)
  133. 		{
  134. 		        make_queue_empty();
  135. 		   		v.clear();
  136. 		   		cout<<"-1"<<"\n";
  137. 		}
  138.  
  139.     }
  140.    return 0;
  141. }
  142.  
Success #stdin #stdout 0.01s 3604KB
comments (?)
stdin
copy 
5 6
1 5 2
1 2 1
2 5 10
1 3 1
3 5 10
1 4 1
4 5 10

5 6
1 5 3
1 2 1
2 5 10
1 3 1
3 5 10
1 4 1
4 5 10

5 6
1 5 4
1 2 1
2 5 10
1 3 1
3 5 10
1 4 1
4 5 10

5 6
1 5 5
1 2 1
2 5 10
1 3 1
3 5 10
1 4 1
4 5 10
3 3

1 3 4

1 3 3

1 2 4

2 3 5

5 6

5 2 5

1 2 2

2 5 4

3 2 3

4 3 1

5 1 3

5 4 2

2 2

1 2 3

1 2 5

2 2 2


5 6

5 2 2

1 2 2

2 5 4

3 2 3

4 3 1

5 1 3

5 4 2
5 6

5 2 3

1 2 2

2 5 4

3 2 3

4 3 1

5 1 3

5 4 2
5 6

5 2 4

1 2 2

2 5 4

3 2 3

4 3 1

5 1 3

5 4 2
5 6

5 2 5

1 2 2

2 5 4

3 2 3

4 3 1

5 1 3

5 4 2
5 6

5 2 6

1 2 2

2 5 4

3 2 3

4 3 1

5 1 3

5 4 2
5 6

5 2 7

1 2 2

2 5 4

3 2 3

4 3 1

5 1 3

5 4 2
5 6

5 2 8

1 2 2

2 5 4

3 2 3

4 3 1

5 1 3

5 4 2
5 6

5 2 9

1 2 2

2 5 4

3 2 3

4 3 1

5 1 3

5 4 2
5 6

5 2 10

1 2 2

2 5 4

3 2 3

4 3 1

5 1 3

5 4 2

0 0
stdout
copy 
11
11
-1
-1
-1
15
9
6
14
15
15
16
23
24
24
24
https://ideone.com/WuY91C
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!