fork download
copy 
  1. #include <iostream>
  2. #include <climits>
  3. using namespace std;
  4.  
  5. int main() {
  6.  
  7. 	long long n,m,q;
  8. 	cin>>n>>m>>q;
  9.  
  10. 	long long DP[n][n];
  11. 	for(long long i=0;i<n;i++)
  12. 	{
  13. 		for(long long j=0;j<n;j++)
  14. 		{
  15. 			if(i != j)
  16. 			{
  17. 				DP[i][j] = LLONG_MAX;
  18. 			}
  19. 			else
  20. 			{
  21. 				DP[i][j]=0;
  22. 			}
  23. 		}
  24. 	}
  25.  
  26. 	for(long long i=0;i<m;i++)
  27. 	{
  28. 		long long a,b,c;
  29. 		cin>>a>>b>>c;
  30.  
  31. 		DP[a-1][b-1]=c;
  32. 		DP[b-1][a-1]=c;
  33. 	}
  34.  
  35. 	for(long long k=0;k<n;k++)
  36. 	{
  37. 		for(long long i=0;i<n;i++)
  38. 		{
  39. 			for(long long j=0;j<n;j++)
  40. 			{
  41. 				if(i!=j && DP[i][k] != LLONG_MAX && DP[k][j] != LLONG_MAX && (DP[i][j] > DP[i][k] + DP[k][j]))
  42. 				{
  43. 					DP[i][j] = DP[i][k] + DP[k][j];
  44. 				}
  45. 			}
  46. 		}
  47. 	}
  48.  
  49. 	for(long long i=0;i<q;i++)
  50. 	{
  51. 		long long a,b;
  52. 		cin>>a>>b;
  53.  
  54. 		if(DP[a-1][b-1] == LLONG_MAX)
  55. 		{
  56. 			cout<<-1<<endl;
  57. 		}
  58. 		else
  59. 		{
  60. 			cout<<DP[a-1][b-1]<<endl;
  61. 		}
  62.  
  63. 	}
  64.  
  65.  
  66. 	return 0;
  67. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
4 3 5
1 2 5
1 3 9
2 3 3
1 2
2 1
1 3
1 4
3 2
stdout
copy 
5
5
8
-1
3
https://ideone.com/s43Ehs
language:
C++14 (gcc 8.3)
created:
4 days 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!