fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int n,m,a,b,d[4][100005],dis[7][7][100005];
  5. vector <pair<int,int>> ve[100005],vec[100005];
  6. void DIJ()
  7. {
  8.     priority_queue <pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> q;
  9.     for (int u=1;u<=n;u++) for (int i=0;i<=a;i++) d[i][u]=1e18;
  10.     d[0][1]=0,q.push({0,{1,0}});
  11.     while (q.size())
  12.     {
  13.         int c_w=q.top().first;
  14.         int u=q.top().second.first,mx=q.top().second.second;
  15.         q.pop();
  16.         if (d[mx][u]<c_w) continue;
  17.         for (pair <int,int> p : ve[u])
  18.         {
  19.             int v=p.first,w=p.second;
  20.             if (d[mx][v]>d[mx][u]+w) d[mx][v]=d[mx][u]+w,q.push({d[mx][v],{v,mx}});
  21.             if (mx<a && d[mx+1][v]>d[mx][u]) d[mx+1][v]=d[mx][u],q.push({d[mx+1][v],{v,mx+1}});
  22.         }
  23.     }
  24. }
  25. void DIJDL()
  26. {
  27.     priority_queue <pair<pair<int,int>,pair<int,int>>,vector<pair<pair<int,int>,pair<int,int>>>,greater<pair<pair<int,int>,pair<int,int>>>> q;
  28.     for (int u=1;u<=n;u++) for (int s=0;s<=b+1;s++) for (int r=0;r<=b+1;r++) dis[s][r][u]=1e18;
  29.     for (int u=1;u<=n;u++) for (int j=0;j<=a;j++) dis[0][0][u]=min(dis[0][0][u],d[j][u]);
  30.     for (int u=1;u<=n;u++) if (dis[0][0][u]!=1e18) q.push({{dis[0][0][u],0},{u,0}});
  31.     while (!q.empty())
  32.     {
  33.         int c_w=q.top().first.first,r=q.top().first.second;
  34.         int u=q.top().second.first,s=q.top().second.second;
  35.         q.pop();
  36.         if (dis[s][r][u]<c_w) continue;
  37.         for (pair <int,int> p : vec[u])
  38.         {
  39.             int v=p.first,w=p.second;
  40.             int nexts=min(s+1,b+1);
  41.             if (dis[nexts][r][v]>dis[s][r][u]+w) dis[nexts][r][v]=dis[s][r][u]+w,q.push({{dis[nexts][r][v],r},{v,nexts}});
  42.             if (r<b && dis[nexts][r+1][v]>dis[s][r][u]+2*w) dis[nexts][r+1][v]=dis[s][r][u]+2*w,q.push({{dis[nexts][r+1][v],r+1},{v,nexts}});
  43.         }
  44.     }
  45.     for (int u=2;u<=n;u++)
  46.     {
  47.         int res=dis[b+1][b][u];
  48.         for (int s=0;s<=b;s++) res=min(res,dis[s][s][u]);
  49.         if (res!=1e18) cout<<res<<' ';
  50.         else cout<<-1<<' ';
  51.     }
  52. }
  53. signed main()
  54. {
  55.     ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  56.      freopen("HELP.INP","r",stdin);
  57.      freopen("HELP.OUT","w",stdout);
  58.     cin>>n>>m>>a>>b;
  59.     for (int i=1;i<=m;i++)
  60.     {
  61.         int u,v,w;
  62.         cin>>u>>v>>w;
  63.         ve[u].push_back({v,w});
  64.         vec[v].push_back({u,w});
  65.     }
  66.     DIJ(),DIJDL();
  67.     return 0;
  68. }
Success #stdin #stdout 0.01s 12364KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SlQ9V0
language:
C++14 (gcc 8.3)
created:
4 days 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!