func_code_string: #include <bits/stdc++.h>   using namespace std;   const int N = 66666;   const int M = 55;   const int sM = 105;   const int inf = 1e9 + 7;   const double pi = acos(-1);   inline int read() {     int x = 0, f = 1;     char ch = getchar();     while (!isdigit(ch)) {       if (ch ==  - ) f = -1;       ch = getchar();     }     while (isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();     return x * f;   }   int lim, pp[N];   struct CP {     double x, y;     CP(double xx = 0, double yy = 0) { x = xx, y = yy; }   };   CP operator+(CP aa, CP bb) { return CP(aa.x + bb.x, aa.y + bb.y); }   CP operator-(CP aa, CP bb) { return CP(aa.x - bb.x, aa.y - bb.y); }   CP operator*(CP aa, CP bb) {     return CP(aa.x * bb.x - aa.y * bb.y, aa.x * bb.y + aa.y * bb.x);   }   void FFT(CP *f, int flag) {     for (int i = (0), iE = (lim - 1); i <= iE; i++)       if (i < pp[i]) swap(f[i], f[pp[i]]);     for (int i = 2; i <= lim; i <<= 1) {       CP ch(cos(2 * pi / i), flag * sin(2 * pi / i));       for (int l = (i >> 1), j = 0; j < lim; j += i) {         CP now(1, 0);         for (int k = j; k < j + l; k++) {           CP pa = f[k], pb = now * f[k + l];           f[k] = pa + pb, f[k + l] = pa - pb, now = now * ch;         }       }     }     if (flag == -1)       for (int i = (0), iE = (lim - 1); i <= iE; i++)         f[i].x /= lim, f[i].y /= lim;   }   CP A[N], B[N];   int n, m, t, x, dis[N];   int fu[N], fv[N], fval[N];   double ans[M][N], p[sM][N], calc[sM][N];   void Solve(int l, int mid, int r) {     for (int d = (1), dE = (m); d <= dE; d++) {       int tota = -1, totb = 0;       B[0] = CP(0, 0);       for (int i = (l), iE = (mid); i <= iE; i++)         A[++tota] = CP(ans[fv[d]][i], 0);       for (int i = (1), iE = (min(r - l + 1, t)); i <= iE; i++)         B[++totb] = CP(p[d][i], 0);       for (lim = 1; lim <= tota + totb; lim <<= 1)         ;       for (int i = (0), iE = (lim - 1); i <= iE; i++)         pp[i] = ((pp[i >> 1] >> 1) | ((i & 1) * (lim >> 1)));       for (int i = (tota + 1), iE = (lim - 1); i <= iE; i++) A[i] = CP(0, 0);       for (int i = (totb + 1), iE = (lim - 1); i <= iE; i++) B[i] = CP(0, 0);       FFT(A, 1), FFT(B, 1);       for (int i = (0), iE = (lim - 1); i <= iE; i++) A[i] = A[i] * B[i];       FFT(A, -1);       for (int i = (1), iE = (r - mid); i <= iE; i++)         calc[d][i + mid] += A[i + tota].x;     }   }   void Divide(int l, int r) {     if (l == r) {       for (int j = (1), jE = (m); j <= jE; j++)         ans[fu[j]][l] = min(ans[fu[j]][l], calc[j][l] + fval[j]);       return;     }     int mid = (l + r) / 2;     Divide(l, mid);     Solve(l, mid, r);     Divide(mid + 1, r);   }   int main() {     n = read(), m = read(), t = read(), x = read();     dis[n] = 0;     for (int i = (1), iE = (n - 1); i <= iE; i++) dis[i] = inf;     for (int i = (1), iE = (n - 1); i <= iE; i++)       for (int j = (t), jE = (t * 2); j <= jE; j++) ans[i][j] = inf;     for (int i = (1), iE = (m); i <= iE; i++) {       fu[i] = read(), fv[i] = read(), fval[i] = read();       for (int j = (1), jE = (t); j <= jE; j++) p[i][j] = 1. * read() / 100000;     }     for (int i = (1), iE = (n); i <= iE; i++)       for (int j = (1), jE = (m); j <= jE; j++)         dis[fu[j]] = min(dis[fu[j]], dis[fv[j]] + fval[j]);     for (int i = (1), iE = (n); i <= iE; i++)       for (int j = (0), jE = (t - 1); j <= jE; j++) ans[i][j] = dis[i] + x;     Solve(0, t - 1, t * 2);     Divide(t, t * 2);     printf( %.10lf n , ans[1][2 * t]);     return 0;   }   