fork download
  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
stdin
3 3
1 2 1 6
2 3 2 6
3 1 3 6
stdout
6 2