fork download
copy 
  1. #include <vector>
  2. #include <iostream>
  3.  
  4. #define INF (1LL << 60)
  5.  
  6. using namespace std;
  7.  
  8. int main()
  9. {
  10. 	int V, E, A, B; long long F, T;
  11.  
  12. 	scanf("%d", &V);
  13. 	scanf("%d", &E);
  14.  
  15. 	vector<vector<long long> > G(V, vector<long long>(V, INF));
  16.  
  17. 	vector<vector<long long> > H(V, vector<long long>(V, INF));
  18.  
  19. 	for (int i = 0; i < E; i++)
  20. 	{
  21. 		scanf("%d", &A);
  22. 		scanf("%d", &B);
  23.  
  24. 		scanf("%lld", &F);
  25. 		scanf("%lld", &T);
  26.  
  27. 		G[A - 1][B - 1] = F; H[A - 1][B - 1] = T;
  28. 		G[B - 1][A - 1] = F; H[B - 1][A - 1] = T;
  29. 	}
  30.  
  31. 	vector<vector<pair<long long, long long> > > dp(V, vector<pair<long long, long long> >(1 << V, make_pair(INF, 0))); dp[0][0] = make_pair(0, 1);
  32.  
  33. 	for (int i = 1; i < (1 << V); i++)
  34. 	{
  35. 		for (int j = 0; j < V; j++) // start
  36. 		{
  37. 			if (i & (1 << j))
  38. 			{
  39. 				for (int k = 0; k < V; k++) // end
  40. 				{
  41. 					if (G[j][k] != INF)
  42. 					{
  43. 						long long cost = dp[j][i - (1 << j)].first + G[j][k];
  44.  
  45. 						if (cost <= H[j][k])
  46. 						{
  47. 							if (dp[k][i].first > cost)
  48. 							{
  49. 								dp[k][i] = make_pair(cost, 0);
  50. 							}
  51.  
  52. 							if (dp[k][i].first == cost)
  53. 							{
  54. 								dp[k][i].second += dp[j][(i - (1 << j))].second;
  55. 							}
  56. 						}
  57. 					}
  58. 				}
  59. 			}
  60. 		}
  61. 	}
  62.  
  63. 	if (dp[0][(1 << V) - 1].first != INF)
  64. 	{
  65. 		printf("%lld %lld\n", dp[0][(1 << V) - 1].first, dp[0][(1 << V) - 1].second);
  66. 	}
  67. 	else
  68. 	{
  69. 		printf("IMPOSSIBLE\n");
  70. 	}
  71.  
  72. 	return 0;
  73. }
Success #stdin #stdout 0s 3420KB
comments (?)
stdin
copy 
3 3
1 2 1 6
2 3 2 6
3 1 3 6
stdout
copy 
6 2
https://ideone.com/ga9XBw
language:
C++14 (gcc 8.3)
created:
8 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!