fork download
copy 
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5. #define M 100009
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9. struct pp{
  10.     ll data;
  11.     int pos;
  12.     pp(){}
  13.     pp(ll a,int b){
  14.         data=a; pos=b;
  15.     }
  16.     bool operator<(const pp &q)const{
  17.         return data > q.data;
  18.     }
  19. };
  20. vector<pp> v[M];
  21. priority_queue<pp> q;
  22. int n,m,k,chk[M];
  23. ll d[M][13];
  24. int main(){
  25.     int i,j;
  26.     scanf("%d %d %d",&n,&m,&k);
  27.     for (i=1;i<=m;i++){
  28.         int a,b;
  29.         ll c;
  30.         scanf("%d %d %lld",&a,&b,&c);
  31.         v[a].push_back(pp(c,b)); v[b].push_back(pp(c,a));
  32.     }
  33.  
  34.     for (i=1;i<=n;i++) for (j=1;j<=k+1;j++) d[i][j]=-1;
  35.     d[1][1]=0;
  36.     q.push(pp(0,1));
  37.     while(!q.empty()){
  38.         pp now=q.top(); q.pop();
  39.  
  40.         if (d[now.pos][k] < now.data && d[now.pos][k]!=-1) continue;
  41.  
  42. //        if (d[now.pos][k]!=-1) chk[now.pos]=1;
  43.  
  44.         for (auto there:v[now.pos]){
  45. //            if (chk[there.pos]) continue;
  46.             for (j=1;j<=k+1;j++)
  47.                 if (d[there.pos][j]==-1) break;
  48.             d[there.pos][j]=now.data+there.data;
  49.             while(j>1 && d[there.pos][j] < d[there.pos][j-1]) swap(d[there.pos][j],d[there.pos][j-1]),j--;
  50.             d[there.pos][k+1]=-1;
  51.             if (j<=k) q.push(pp(now.data+there.data,there.pos));
  52.         }
  53.     }
  54.     printf("%lld",d[n][k]);
  55. }
Success #stdin #stdout 0s 15200KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8sbg5V
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!