fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int main() {
  6. 	while(1)
  7. 	{
  8. 		long long int row,col;
  9. 		cin>>row>>col;
  10. 		if(row==0&&col==0)
  11. 		break;
  12. 		long long int graph[row][row];
  13. 		vector<pair<long long int,long long int>>dist(row);
  14. 		for(int i=0;i<row;i++)
  15. 		for(int j=0;j<row;j++)
  16. 		{
  17. 			graph[i][j] = INT_MAX;
  18. 			dist[j].second=(-1);
  19. 		}
  20. 		long long int src,end;
  21. 		cin>>src>>end;
  22. 		for(int i=0;i<col;i++)
  23. 		{
  24. 			long long int u,v,w;
  25. 			cin>>u>>v>>w;
  26. 			graph[u][v] = w;
  27. 			dist[v].second = u;
  28. 		}
  29. 		/*for(int i=0;i<row;i++){
  30. 		for(int j=0;j<row;j++)
  31. 		cout<<graph[i][j]<<" ";
  32. 		cout<<endl;}*/
  33. 		long long int count=0,save,parent[row],t=2,flag=0;
  34. 		bool visited[row];
  35. 		for(int i=0;i<row;i++)
  36. 		parent[i] = (-1);
  37. 		//parent[src] = (-1);
  38. 		while(1){
  39. 		flag++;
  40. 		memset(visited,false,sizeof(visited));
  41. 		for(int i=0;i<row;i++)
  42. 		dist[i].first=INT_MAX,parent[i] = (-1);
  43. 		dist[src].first=0;dist[src].second=src;parent[src] = src;
  44. 		for(int i=0;i<row;i++)
  45. 		{
  46. 			int crt =-1;
  47. 			for(int j=0;j<row;j++)
  48. 			{
  49. 				if(visited[j]==true)
  50. 				continue;
  51. 				else if(crt==(-1)||dist[crt].first>dist[j].first)
  52. 				crt=j;
  53. 			}//cout<<crt<<" ";
  54. 			visited[crt] = true;
  55. 			for(int j=0;j<row;j++)
  56. 			{
  57. 				if(graph[crt][j]>=0)
  58. 				if(dist[j].first>dist[crt].first+graph[crt][j]&&graph[crt][j]!=INT_MAX)
  59. 				dist[j].first = dist[crt].first+graph[crt][j],parent[j] = crt;//cout<<crt<<j<<" ";
  60. 				//cout<<endl;
  61. 			}
  62.  
  63.  
  64. 		}
  65. 		int k=end;
  66. 		while(k!=src&&parent[k]!=(-1))
  67. 		{
  68. 			graph[parent[k]][k]=(INT_MAX);
  69. 			count++;
  70. 			k = parent[k];
  71. 			if(k==(-1))
  72. 			{
  73. 				cout<<"-1"<<endl;
  74. 				break;
  75. 			}
  76.  
  77. 		}
  78. 		//cout<<endl;
  79. 		if(dist[end].first==INT_MAX&&count<=col)
  80. 		{
  81. 			cout<<"-1"<<endl;
  82. 			break;
  83. 		}
  84. 		else if(flag==1)
  85. 		save = dist[end].first;
  86. 		else if(save<dist[end].first&&count<=col)
  87. 		{
  88. 			cout<<dist[end].first<<endl;
  89. 			break;
  90. 		}
  91. 		else if(count>col)
  92. 		{
  93. 			cout<<"-1"<<endl;
  94. 			break;
  95. 		}
  96. 		}
  97. 	}
  98. 	// your code goes here
  99. 	return 0;
  100. }
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
4 10
1 3
3 1 68
2 3 79
0 2 164
3 1 118
3 0 97
1 3 145
0 3 52
1 2 169
1 0 79
1 3 230
0 0
stdout
copy 
230
https://ideone.com/LSaQve
language:
C++14 (gcc 8.3)
created:
6 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!