C++14(g++5.4) 解法, 执行用时: 321ms, 内存消耗: 1308K, 提交时间: 2020-07-18 18:55:18

#include<bits/stdc++.h>
using namespace std;
const int MOD = 19260817, N = 111;
int p;
void add(int &x, int y) {
  x += y;
  if(x >= MOD) x -= MOD;
}
void sub(int &x, int y) {
  x -= y;
  if(x < 0) x += MOD;
}
struct mat {
  int a[N][N];
  mat() {
    memset(a, 0, sizeof a);
  }
  int* operator[](const int &x) {
    return a[x];
  }
  const int* operator[](const int &x) const {
    return a[x];
  }
  friend mat operator*(const mat &x, const mat &y) {
    mat z;
    for(int i = 0; i < p; i++) {
      for(int j = 0; j < p; j++) {
        for(int k = 0; k < p; k++) {
          add(z[i][j], 1ll * x[i][k] * y[k][j] % MOD);
        }
      }
    }
    return z;
  }
};
int siz[N], inv[50005];
vector<pair<int, int>> edg[N];
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  inv[1] = 1;
  for(int i = 2; i < 50005; i++) {
    inv[i] = 1ll * (MOD - MOD / i) * inv[MOD % i] % MOD;
  }
  int n, m, k; cin >> n >> m >> k;
  p = n + 1;
  for(int i = 0; i < m; i++) {
    int u, v, w; cin >> u >> v >> w;
    // assert(w >= 0 && w < 19260817);
    u--, v--;
    edg[u].emplace_back(v, w);
    siz[u]++;
  }
  for(int i = 0; i < n; i++) {
    if(siz[i] == 0) {
      edg[i].emplace_back(i, 0);
      siz[i]++;
    }
  }
  mat ans, a;
  for(int i = 0; i < p; i++) {
    ans[i][i] = 1;
  }
  a[n][n] = 1;
  for(int i = 0; i < n; i++) {
    for(const pair<int, int> &pir: edg[i]) {
      const int u = i, v = pir.first, w = pir.second;
      add(a[u][v], inv[siz[u]]);
      add(a[u][n], 1ll * w * inv[siz[u]] % MOD);
    }
  }
  while(k) {
    if(k & 1) {
      ans = ans * a;
    }
    a = a * a;
    k >>= 1;
  }
  int res = 0;
  for(int i = 0; i < n; i++) {
    add(res, ans[i][n]);
  }
  res = 1ll * res * inv[n] % MOD;
  cout << res << '\n';
}