fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ; 
  3.  
  4.  
  5. #define ll long long 
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define fir first 
  8. #define sec second 
  9. #define piint pair < int , int >
  10. #define FOR( i , a , b ) for (int i = (a) , _b = (b) ; i <= _b ; i ++ )  
  11. #define pb push_back 
  12. #define str string 
  13. #define ALL(a) (a).begin() , (a).end() 
  14. #define rep( i , a , b) for (int i = (a) ; i < (b) ; i ++ )
  15. #define ld long double
  16. const int maxn = 1e5 ;
  17. #define debug 0
  18. #define oo (ll)(1e18)
  19.  
  20.  
  21. int x[maxn+3] , y[maxn+3] ;
  22.  
  23. ll d[503][503] ;
  24. vector < pair < int , ll > > a[maxn+3] ;
  25. int n , m ; 
  26. int q ; 
  27.  
  28. // void ijk ( int st ) 
  29. // {
  30.  
  31.  
  32. // 	FOR ( i , 0 , n ) {
  33. // 		dp[i][st] = oo ;
  34. // 	}
  35. // 	dp[st][st] = 0 ;
  36. // 	#define T pair < ll , int > 
  37. // 	priority_queue < T ,std::vector<T> , greater < T > > q ;
  38. // 	q.push ( { 0 , st }) ;
  39. // 	while (q.size()){
  40. // 		auto [du , u ] = q.top() ;
  41. // 		q.pop() ;
  42. // 		if ( du > d[u][st]) continue ;
  43. // 		for (auto [ v , w ] : a[u] ){
  44. // 			if ( d[v][st] > d[u][st] + w ) {
  45. // 				d[v][st] = d[u][st] + w ;
  46. // 				q.push ( { v , d[v][st] } ); 
  47. // 			}
  48. // 		}
  49. // 	}
  50. // }
  51. ll dp[maxn+3][503] ;
  52. bool save[503][503] ;
  53. void sub1(){
  54. 	// FOR ( i , 1 , n ) ijk ( i ) ;
  55. 	FOR ( k , 1 , n ) 
  56. 	FOR ( i , 1 , n ) 
  57. 	FOR ( j , 1 , n ) 
  58. 	if( d[i][j] != oo && d[k][j] != oo ){
  59. 		d[i][j] = min ( d[i][j] , d[i][k] + d[k][j]) ;
  60. 	}
  61. 	memset ( dp , -1 , sizeof (dp) ) ;
  62. 	dp[0][1] = 0 ;
  63. 	ll res = 0 ;
  64. 	FOR ( i , 1 , q ) {
  65. 		int X_I = x[i] ;
  66. 		int Y_I = y[i] ;
  67. 		FOR ( u ,1 ,  n ) {
  68. 			if ( dp[i-1][u] == -1 ) continue ;
  69. 			else {
  70. 				dp[i][u] = max ( dp[i][u] , dp[i-1][u] ) ;
  71. 				res = max ( res , dp[i][u]) ;
  72. 				if ( (save[u][X_I]||u==X_I) && d[X_I][Y_I] != oo ){
  73. 					ll val = d[X_I][Y_I] ;
  74. 					dp[i][Y_I] = max ( dp[i][Y_I] , dp[i-1][u]+val) ;
  75. 					res = max ( res , dp[i][Y_I ]) ;
  76. 				}
  77. 			}
  78. 		}
  79. 	}
  80. 	cout << res ;
  81.  
  82. }
  83. #define name "TASK" 
  84. int main(){
  85.     fast 
  86.     if(fopen(name".INP","r")) {
  87.         freopen (name".INP","r",stdin);
  88.         freopen (name".OUT","w",stdout);
  89.     }
  90.     cin >> n>> m ;
  91.     cin >> q; 
  92. 	FOR ( i , 1 , n )
  93. 	FOR ( j , 1 , n ) 
  94. 	if(i==j)continue ;
  95. 	else d[i][j] = oo ;
  96.     FOR ( i , 1 , m ) {
  97.     	ll u , v , w ; cin >> u >> v >> w ;
  98.     	d[u][v] = d[v][u] = min ( d[u][v] , w );
  99.     	save[u][v] = save[v][u] = 1; 
  100.     	a[u].pb ( { v , w }) ;
  101.     	a[v].pb ( { u , w }) ;
  102.     }
  103.     FOR ( i , 1 , q ) {
  104.  
  105.     	cin >> x[i] >> y[i] ;
  106.  
  107.     }
  108.     if ( n <= 500 ) sub1() ;
  109.  
  110.     cerr << "\nTIME: = " << (1.0*clock())/CLOCKS_PER_SEC << '\n';
  111.     return(0) ;
  112. }
Success #stdin #stdout #stderr 0.06s 400108KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
TIME: = 0.058642
https://ideone.com/3b9tXb
language:
C++14 (gcc 8.3)
created:
1 day 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!