fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty