fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define pii pair<int, int>
  3. #define mp make_pair
  4. #define INF 1000000007
  5.  
  6. using namespace std;
  7.  
  8. int dp[101][10001];
  9.  
  10. struct node{
  11. 	int dist, cost, src;
  12.  
  13. 	node(int d, int c, int s) : dist(d), cost(c), src(s){}
  14. };
  15.  
  16. vector<node> adj[101];
  17.  
  18. int n, k, dist_0[101];
  19.  
  20. void build(){
  21. 	for(int j = 0; j < 101; j++)
  22. 		adj[j].clear(), dist_0[j] = INF;
  23.  
  24. 	vector< pair<pii, int> > zero;
  25. 	int m;
  26. 	scanf("%d %d %d",&k ,&n ,&m);
  27. 	while(m--){
  28. 		int u, v, cost, dist;
  29. 		scanf("%d %d %d %d" ,&u ,&v ,&dist ,&cost);
  30. 		adj[v].push_back(node(dist, cost, u));
  31. 		if(cost == 0) zero.push_back(mp(mp(u, v), dist));
  32. 	}
  33.  
  34.     dist_0[1] = 0;
  35. 	// BELLMEN FORD
  36. 	for(int j = 0; j < n-1; j++){
  37. 		for(int i = 0; i < zero.size(); i++){
  38. 			int u = zero[i].first.first, v = zero[i].first.second, dist = zero[i].second;
  39. 			if(dist_0[u] + dist < dist_0[v]) dist_0[v] = dist_0[u] + dist;
  40. 		}
  41. 	}
  42. }
  43.  
  44. int solve(){
  45. 	for(int j = 0; j < 101; j++)
  46. 		for(int i = 0; i < 10001; i++)
  47. 			if(j != 1) dp[j][i] = INF;
  48. 			else dp[j][i] = 0;
  49.  
  50. 	for(int j = 1; j <= n; j++)
  51. 		dp[j][0] = dist_0[j];
  52.  
  53. 	for(int j = 1; j <= k; j++){
  54. 		for(int i = 2; i <= n; i++){
  55. 			for(int l = 0; l < adj[i].size(); l++){
  56. 				node curr = adj[i][l];
  57. 				//dp[i][j] = min(dp[i][j], dp[i][j - 1]);
  58. 				if(j - curr.cost >= 0) dp[i][j] = min(dp[i][j], dp[curr.src][j - curr.cost] + curr.dist);
  59. 			}
  60. 		}
  61. 	}
  62.  
  63. 	int ans = INF;
  64. 	for(int j = 0; j <= k; j++)
  65. 		ans = min(ans, dp[n][j]);
  66. 	if(ans == INF) return -1;
  67. 	return ans;
  68. }
  69.  
  70. int main(){
  71. 	int t;
  72. 	scanf("%d",&t);
  73. 	while(t--){
  74. 		build();
  75. 		//cout << "builder completes!\n";
  76. 		printf("%d\n",solve());
  77. 	}
  78. 	return 0;
  79. }
  80.  
Success #stdin #stdout 0.01s 7160KB
comments (?)
stdin
copy 
2
5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2
0
4
4
1 4 5 2
1 2 1 0
2 3 1 1
3 4 1 0
stdout
copy 
11
-1
https://ideone.com/pE06ol
language:
C++14 (gcc 8.3)
created:
6 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!