fork download
copy 
  1. #include<stdio.h>
  2. #include<list>
  3. using namespace std;
  4. long long arr[10000][10000];
  5. long long minimum(long long a,long long b)
  6. {
  7. 	if(a<b)
  8. 		return a;
  9. 	else
  10. 		return b;
  11. }
  12. void bfs(long long start,long long n,long long end)
  13. {
  14. 	long long visit[n],cost[n];
  15. 	for(long long i=0;i<n;i++)
  16. 		visit[i]=0,cost[i]=0;
  17. 	list <long long> abc;
  18. 	abc.push_back(start);
  19.  
  20. 	while(!abc.empty())
  21. 	{
  22. 		long long front=abc.front();
  23. 		abc.pop_front();
  24. 		for(long long i=0;i<n;i++)
  25. 		{
  26. 			if(arr[front][i]!=0)
  27. 			{
  28. 				if(visit[i]==0)
  29. 				{
  30. 					visit[i]=1;
  31. 					cost[i]=arr[front][i];
  32. 				}
  33. 				else
  34. 				{
  35. 					cost[i]=minimum(cost[i],cost[front]+arr[front][i]);
  36. 				}
  37. 			}
  38. 		}
  39. 	}
  40. 	if(visit[end])
  41. 		printf("%lld\n",cost[end]);
  42. 	else
  43. 		printf("NONE\n");
  44. }
  45. int main()
  46. {
  47. 	long long test,s,e,d,b,g,m,n;
  48. 	scanf("%lld",&test);
  49. 	while(test--)
  50. 	{
  51. 		scanf("%lld%lld%lld%lld",&n,&m,&b,&g);
  52. 		b--;
  53. 		g--;
  54. 		for(long long i=0;i<n;i++)
  55. 		for(long long j=0;j<n;j++)
  56. 			arr[i][j]=0;
  57. 		while(m--)
  58. 		{
  59. 			scanf("%lld%lld%lld",&s,&e,&d);
  60. 			s--;
  61. 			e--;
  62. 			arr[s][e]=arr[e][s]=d;
  63. 		}
  64. 		bfs(b,n,g);
  65. 	}
  66. 	return 0;
  67. }
Runtime error #stdin #stdout 0.62s 784384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JKPyIE
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!