fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Case 1 solved!
https://ideone.com/GAupqJ
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!