fork(1) download
  1. //itisalways42
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. typedef long long int LL;
  7. typedef pair<LL,LL> II;
  8. typedef vector< II > VII;
  9. typedef vector<int> VI;
  10. typedef vector< VI > VVI;
  11. typedef vector< VII > mat;
  12.  
  13. #define PB push_back
  14. #define MP make_pair
  15. #define F first
  16. #define S second
  17. #define SZ(a) (int)(a.size())
  18. #define ALL(a) a.begin(),a.end()
  19. #define SET(a,b) memset(a,b,sizeof(a))
  20.  
  21. #define si(n) scanf("%d",&n)
  22. #define dout(n) printf("%d\n",n)
  23. #define sll(n) scanf("%lld",&n)
  24. #define lldout(n) printf("%lld\n",n)
  25. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  26.  
  27. #define TRACE
  28.  
  29. #ifdef TRACE
  30. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  31. template <typename Arg1>
  32. void __f(const char* name, Arg1&& arg1){
  33. cerr << name << " : " << arg1 << std::endl;
  34. }
  35. template <typename Arg1, typename... Args>
  36. void __f(const char* names, Arg1&& arg1, Args&&... args){
  37. const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  38. }
  39. #else
  40. #define trace(...)
  41. #endif
  42.  
  43. //FILE *fin = freopen("in","r",stdin);
  44. //FILE *fout = freopen("out","w",stdout);
  45.  
  46. const int N = int(500)+10;
  47. const LL INF = LL(1e15);
  48. const LL MOD = LL(1e9)+7;
  49. int n;
  50. int g[N][N];
  51.  
  52. void mult(mat &a, mat &b)
  53. {
  54. mat ret(n,VII(n,MP(INF,0)));
  55. for(int i=0; i<n; i++)
  56. for(int j=0; j<n; j++)
  57. {
  58. LL mn=INF;
  59. for(int k=0; k<n; k++)
  60. if(a[i][k].F + b[k][j].F < mn)
  61. mn = a[i][k].F + b[k][j].F;
  62. ret[i][j].F = mn;
  63. for(int k=0; k<n; k++)
  64. if(a[i][k].F + b[k][j].F == mn)
  65. ret[i][j].S = (ret[i][j].S + a[i][k].S*b[k][j].S)%MOD;
  66. }
  67. a = ret;
  68. }
  69.  
  70. mat ret;
  71. void expo(int k)
  72. {
  73. ret.resize(n, VII(n, MP(INF, 0)));
  74.  
  75. for(int i=0; i<n; i++) ret[i][i] = MP(0,1);
  76. mat a(n,VII(n));
  77. for(int i=0; i<n; i++)
  78. for(int j=0; j<n; j++)
  79. if(g[i][j])
  80. a[i][j] = MP(g[i][j],1);
  81. else
  82. a[i][j] = MP(INF,0);
  83. while(k)
  84. {
  85. if(k&1) mult(ret,a);
  86. mult(a,a);
  87. k /= 2;
  88. }
  89. }
  90.  
  91. int main()
  92. {
  93. fast_io;
  94. int m,k;
  95. cin>>n>>m>>k;
  96. for(int i=0; i<m; i++)
  97. {
  98. int u,v,w;
  99. cin>>u>>v>>w;
  100. u--, v--;
  101. g[u][v] = g[v][u] = w;
  102. }
  103. expo(k);
  104. for(int i=0; i<n; i++)
  105. {
  106. for(int j=0; j<n; j++)
  107. {
  108. if(ret[i][j].F == INF) cout<<"X "<<0<<" ";
  109. else cout<<ret[i][j].F<<" "<<ret[i][j].S<<" ";
  110. }
  111. cout<<"\n";
  112. }
  113. return 0;
  114. }
  115.  
Runtime error #stdin #stdout 0s 4476KB
stdin
Standard input is empty
stdout
Standard output is empty