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
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/9r975m
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!