fork download
copy 
  1. // There is nothing in a caterpillar that tells you its going to be a butterfly --------------------- !
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define rep(i,n) for(int i=0;i<n;i++)
  5. #define ll  long long int
  6. #define pi pair<ll,ll>
  7. #define pii pair<ll,pi>
  8. #define f first
  9. #define mp make_pair
  10. #define mod 1000000007
  11. #define s second
  12. #define pb push_back
  13.  
  14. vector<pi>g[100011];
  15. ll d[100011];
  16. ll dp[100011]={0};
  17. vector<int>P[100011];
  18. ll inc[100011];
  19. ll K;
  20. ll calc(ll a,ll b){
  21.     if(a<b) swap(a,b);
  22.     double r=(double)K/ (double)a;
  23.     if(b>=r) return K+1;
  24.     return a*b;
  25. }
  26. int main(){
  27.  
  28.     ios_base::sync_with_stdio(0);
  29.     cin.tie(0);
  30.     int N,M;
  31.     int u,v;
  32.     char c;
  33.     cin >> N >> M >> K;
  34.     rep(i,M){
  35.         cin >> u >> v >> c;
  36.         g[u].pb({v,c-'a'});
  37.         g[v].pb({u,c-'a'});
  38.     }
  39.     rep(i,N+1) d[i]=1e18;
  40.     queue<int>q;
  41.     q.push(N);
  42.     int t;
  43.     d[N]=0;
  44.     while(q.size()){
  45.         t=q.front();
  46.         q.pop();
  47.         for(auto x:g[t]){
  48.             if(d[x.f]>d[t]+1){
  49.                 q.push(x.f);
  50.                 d[x.f]=d[t]+1;
  51.             }
  52.         }
  53.     }
  54.     assert(d[1]!=1e18);
  55.     for(int i=1;i<=N;i++){
  56.         if(d[i]<=N){
  57.             P[d[i]].pb(i);
  58.         }
  59.     }
  60.     vector<pi>state;
  61.     state.pb({1,1});
  62.     int cur=0;
  63.     string s="";
  64.     dp[N]=1;
  65.  
  66.     for(int i=1;i<=d[1];i++){
  67.         for(auto x:P[i]){
  68.             for(auto y:g[x]){
  69.                 if(d[y.f]==i-1){
  70.                     dp[x]+=dp[y.f];
  71.                     if(dp[x]>K) dp[x]=K+1;
  72.                 }
  73.             }
  74.         }
  75.         if(P[i].size()==0){
  76.             cout<<-1;
  77.             return 0;
  78.         }
  79.     }
  80.  
  81.     if(dp[1]<K){
  82.         cout<<-1;
  83.         return 0;
  84.     }
  85.  
  86.     while(cur!=d[1]){
  87.         ll sum=0;
  88.         set<pi>ns;
  89.         rep(c,26){
  90.             ll tot=0;
  91.             for(auto x:state){
  92.                 for(auto u:g[x.f]){
  93.                     if(d[u.f]==d[x.f]-1 and u.s==c){
  94.                         tot+=calc(dp[u.f],x.s);
  95.                         if(tot>K) tot=K+1;
  96.                     }
  97.                 }
  98.             }
  99.  
  100.             if(tot>=K){
  101.                 s+=char(c+'a');
  102.                 for(auto x:state){
  103.                     for(auto u:g[x.f]){
  104.                         if(d[u.f]==d[x.f]-1 and u.s==c){
  105.                             ns.erase({u.f,inc[u.f]});
  106.                             inc[u.f]+=x.s;
  107.                             if(inc[u.f]>=K) inc[u.f]=K+1;
  108.                             ns.insert({u.f,inc[u.f]});
  109.                         }
  110.                     }
  111.                 }
  112.                 state.clear();
  113.                 state=vector<pi>(ns.begin(),ns.end());
  114.                 break;
  115.             }
  116.             K-=tot;
  117.         }
  118.         cur++;
  119.     }
  120.     cout<<s;
  121.     return 0;
  122. }
  123.  
Runtime error #stdin #stdout 0s 8104KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MFOZen
language:
C++14 (gcc 8.3)
created:
9 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!