fork(10) download
copy 
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5. #include <functional>
  6.  
  7. #define N 100005
  8.  
  9. using namespace std;
  10.  
  11. typedef pair<long long, int> pli;
  12.  
  13. int n, m,k;
  14. vector<pli> edge[N];
  15. int cnt[N];
  16. priority_queue<long long> dist[N];
  17.  
  18. int main()
  19. {
  20.     scanf("%d %d %d", &n, &m, &k);
  21.     for (int i = 1; i <= m; i++) {
  22.         int x, y, z;
  23.         scanf("%d %d %d", &x, &y, &z);
  24.         edge[x].push_back(make_pair(z, y));
  25.         edge[y].push_back(make_pair(z, x));
  26.     }
  27.     int st = 1;
  28.     int dst = n;
  29.  
  30.     priority_queue<pli, vector<pli>, greater<pli> > pq;
  31.  
  32.     pq.push(make_pair(0, st));
  33.     dist[st].push(0);
  34.  
  35.     while (!pq.empty())
  36.     {
  37.         pli tmp = pq.top();
  38.         pq.pop();
  39.  
  40.         int x = tmp.second;
  41.         long long z = tmp.first;
  42.  
  43.         if (z > dist[x].top()) continue;
  44.  
  45.         for (int i = 0; i < edge[x].size(); i++) {
  46.             int y = edge[x][i].second;
  47.             long long cost = z + edge[x][i].first;
  48.             if (dist[y].size() < k) {
  49.                 dist[y].push(cost);
  50.                 pq.push(make_pair(cost,y));
  51.             }
  52.             else if (dist[y].top() > cost) {
  53.                 dist[y].push(cost);
  54.                 pq.push(make_pair(cost, y));
  55.                 dist[y].pop();
  56.             }       
  57.         }
  58.     }
  59.  
  60.  
  61.     if (dist[dst].size() < k) printf("-1\n");
  62.     else printf("%lld\n", dist[dst].top());
  63.  
  64.  
  65.     return 0;
  66. }
Runtime error #stdin #stdout 0s 6596KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NJYz07
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!