fork download
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5.  
  6. const int N = 128;
  7.  
  8. template < class T, T INF >
  9. struct dijkstra_kth_shortest_path {
  10. struct edge {
  11. int to;
  12. T w;
  13. edge(){}
  14. edge(int a, T b) {
  15. to=a;
  16. w=b;
  17. }
  18. };
  19. struct el {
  20. int vertex;
  21. T cost;
  22. el(){}
  23. el(int a, T b) {
  24. vertex=a;
  25. cost=b;
  26. }
  27. bool operator <(const el &a) const {
  28. return cost>a.cost;
  29. }
  30. };
  31. int n;
  32. vector < vector < edge > > v;
  33. void initialize(int k) {
  34. n=k;
  35. v.assign(n+1,vector < edge > ());
  36. }
  37. void add_edge(int from, int to, T w) {
  38. v[from].push_back(edge(to,w));
  39. }
  40. void run(int start, vector < T > *dist, int k) {
  41. int i,to;
  42. T current_distance,w;
  43. el curr;
  44. priority_queue < el > q;
  45. for(i=1;i<=n;i++) dist[i].clear();
  46. q.push(el(start,0));
  47. while(!q.empty()) {
  48. curr=q.top();
  49. q.pop();
  50. if((int)(dist[curr.vertex].size())>=k) continue;
  51. if(curr.cost>0) dist[curr.vertex].push_back(curr.cost);
  52. for(i=0;i<(int)(v[curr.vertex].size());i++) {
  53. to=v[curr.vertex][i].to;
  54. if((int)(dist[to].size())>=k) continue;
  55. w=v[curr.vertex][i].w;
  56. current_distance=w+curr.cost;
  57. q.push(el(to,current_distance));
  58. }
  59. }
  60. }
  61. };
  62.  
  63. int tests,current_case;
  64. int n,m;
  65. dijkstra_kth_shortest_path < int, 1000000007 > d;
  66. vector < int > dist[N][N];
  67. int q;
  68.  
  69. void message(int current_case) {
  70. //cerr<<"Case "<<current_case<<" solved!"<<endl;
  71. fprintf(stderr, "Case %d solved!\n", current_case);
  72. }
  73.  
  74.  
  75.  
  76. int main() {
  77. //ios_base::sync_with_stdio(false);
  78. //cin.tie(NULL);
  79. int i,x,y,z;
  80.  
  81. tests=1;
  82. //scanf("%d", &tests);
  83. //cin>>tests;
  84. for(current_case=1;current_case<=tests;current_case++) {
  85. scanf("%d %d", &n, &m);
  86. d.initialize(n);
  87. for(i=1;i<=m;i++) {
  88. scanf("%d %d %d", &x, &y, &z);
  89. d.add_edge(x,y,z);
  90. }
  91. for(i=1;i<=n;i++) {
  92. d.run(i,dist[i],100);
  93. }
  94. scanf("%d", &q);
  95. while(q--) {
  96. scanf("%d %d %d", &x, &y, &z);
  97. if((int)(dist[x][y].size())<z) {
  98. printf("-1\n");
  99. }
  100. else {
  101. printf("%d\n", dist[x][y][z-1]);
  102. }
  103. }
  104.  
  105. MESSAGE:
  106. message(current_case);
  107. }
  108.  
  109. return 0;
  110. }
Success #stdin #stdout #stderr 0s 3664KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
Case 1 solved!