func_code_string: #include <bits/stdc++.h>   using namespace std;   template <class T, class U>   void ckmin(T &a, U b) {     if (a > b) a = b;   }   template <class T, class U>   void ckmax(T &a, U b) {     if (a < b) a = b;   }   const int MAXN = 52;   const int MAXM = 113;   const int MAXT = 20013;   const int INF = 1000000007;   const long double EPS = 1e-9;   const long double PI = 3.141592653589793;   vector<complex<long double> > roots;   void gen(int deg) {     roots.resize(deg);     roots[0] = complex<long double>(1, 0);     roots[1] = complex<long double>(cos(2.0 * PI / deg), sin(2.0 * PI / deg));     for (auto i = (2); i < (deg); i++) {       roots[i] = roots[i - 1] * roots[1];     }     return;   }   void fft(vector<complex<long double> > &f) {     int n = ((int)(f).size());     vector<complex<long double> > g(n);     for (int i = n >> 1; i; i >>= 1) {       for (int j = 0; j < n; j += i) {         int t = (j << 1) - (((j << 1) >= n) ? n : 0);         for (auto k = (0); k < (i); k++) {           g[j + k] = f[t + k] + roots[j] * f[t + k + i];         }       }       swap(f, g);     }   }   vector<long double> conv(vector<long double> p, vector<long double> q) {     int siz = ((int)(p).size()) + ((int)(q).size()) - 1,         siz1 = (1 << (32 - __builtin_clz(siz)));     vector<long double> res(siz);     if (((int)(p).size()) <= 100 || ((int)(q).size()) <= 100) {       for (auto i = (0); i < (((int)(p).size())); i++) {         for (auto j = (0); j < (((int)(q).size())); j++) {           res[i + j] += p[i] * q[j];         }       }       return res;     }     vector<complex<long double> > p1(((int)(p).size())), q1(((int)(q).size()));     for (auto i = (0); i < (((int)(p).size())); i++)       p1[i] = complex<long double>(p[i], 0);     for (auto i = (0); i < (((int)(q).size())); i++)       q1[i] = complex<long double>(q[i], 0);     gen(siz1);     p1.resize(siz1);     q1.resize(siz1);     fft(p1);     fft(q1);     for (auto i = (0); i < (siz1); i++) p1[i] *= q1[i];     fft(p1);     for (auto i = (0); i < (siz1); i++) p1[i] /= siz1;     reverse(p1.begin() + 1, p1.end());     for (auto i = (0); i < (siz); i++) {       res[i] = real(p1[i]);     }     return res;   }   int N, M, T, X;   vector<int> edge[MAXN];   int to[MAXM], cost[MAXM];   vector<long double> prob[MAXM], dp[MAXN];   int path[MAXN];   priority_queue<pair<int, int>, vector<pair<int, int> >,                  greater<pair<int, int> > >       pq1;   queue<int> q;   bitset<MAXN> active;   vector<long double> comb(vector<long double> a, vector<long double> b) {     for (auto i = (0); i < (T - 1); i++) b.push_back(b[T]);     reverse((a).begin(), (a).end());     vector<long double> c = conv(a, b);     vector<long double> res(T);     for (auto i = (0); i < (T); i++) {       res[i] = c[T - 1 + i];     }     return res;   }   int32_t main() {     cout << fixed << setprecision(12);     cerr << fixed << setprecision(4);     ios_base::sync_with_stdio(false);     cin.tie(0);     cin >> N >> M >> T >> X;     T++;     for (auto i = (0); i < (M); i++) {       int u, v, c;       cin >> u >> v >> c;       u--;       v--;       edge[v].push_back(i);       to[i] = u;       cost[i] = c;       prob[i].resize(T);       for (auto j = (1); j < (T); j++) {         int x;         cin >> x;         prob[i][j] = 0.00001 * x;       }     }     fill(path, path + N, INF);     path[N - 1] = 0;     pq1.push({0, N - 1});     while (!pq1.empty()) {       int d = pq1.top().first, u = pq1.top().second;       pq1.pop();       if (d != path[u]) {         continue;       }       for (int e : edge[u]) {         int v = to[e];         if (path[v] > d + cost[e]) {           path[v] = d + cost[e];           pq1.push({path[v], v});         }       }     }     for (auto i = (0); i < (N - 1); i++) {       dp[i].resize(T + 1);       fill((dp[i]).begin(), (dp[i]).end(), INF);       dp[i][T] = path[i] + X;     }     dp[N - 1].resize(T + 1);     fill((dp[N - 1]).begin(), (dp[N - 1]).end(), 0);     dp[N - 1][T] = X;     q.push(N - 1);     active[N - 1] = true;     while (!q.empty()) {       int u = q.front();       q.pop();       if (!active[u]) continue;       active[u] = false;       for (int e : edge[u]) {         int v = to[e];         vector<long double> res = comb(prob[e], dp[u]);         bool ins = false;         for (auto j = (0); j < (T); j++) {           res[j] += cost[e];           if (dp[v][j] > res[j] + EPS) {             dp[v][j] = res[j];             ins = true;           }         }         if (ins && !active[v]) {           active[v] = true;           q.push(v);         }       }     }     cout << dp[0][0] <<   n ;     return 0;   }   