fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int LL;
  4. typedef unsigned long long int uLL;
  5. inline int _Int() { int x; scanf("%d",&x); return x; }
  6. LL bigMod(LL A,LL P,int M){ LL R=1; for(A%=M; P; P>>=1) { if(P&1) R=(R*A)%M; A=(A*A)%M; } return R; } /** (A^P) % M **/
  7. LL bigMul(LL A,LL B,LL M) { LL R=0; for(A%=M; B; B>>=1) { if(B&1) R=(R+A)%M; A=(A+A)%M; } return R; } /** (A*B) % M **/
  8. LL negMod(LL A,LL B) { return ( ( ( A % B ) + B) % B ); } /** (A % B) when A is negative or positive **/
  9. LL invMod(LL A,LL M) { return bigMod( A , M-2, M ); } /** (A^(-1)) % M */
  10. uLL _pow(uLL A,int P) { uLL R=1; for(; P; P>>=1) { if(P&1) R=(R*A); A=(A*A); } return R; } /** (A^P) **/
  11. template<class T>T GCD(T x, T y) { while(x) x^=y^=x^=y%=x; return y; } /** Greatest Common Divisor( a , b ) **/
  12. template<class T> bool inRng( T u, T v, T x ) { return u<=x && x<=v; } /** check ( u <= x <=v ) */
  13. #define myMemset(a,b) memset(a,b,sizeof(a))
  14. #define pi            acos(-1)
  15. #define pb            push_back
  16. #define myDebug(x)    cout<<#x<<" : "<<x<<"\n"
  17. /*************************************************************************************************************************
  18. **                                            Syed Zafrul Lipu (ShockProof)                                              *
  19. **                                            CSE, University of Asia Pacific                                            *
  20. **************************************************************************************************************************/
  21.  
  22. const int M = 500 + 7;
  23. const int inf = 1000000;
  24.  
  25. int inp[M][M];
  26. int G[M][M];
  27.  
  28. bool present[M];
  29.  
  30. void Main()
  31. {
  32.         int n = _Int();
  33.         for(int i = 0; i < n; i ++ ) {
  34.                 for(int j = 0; j < n ;  j ++ ) {
  35.                         G[i][j] = inf;
  36.                         inp[i][j] = _Int();
  37.                 }
  38.         }
  39.         stack<int> st, Ans;
  40.         for(int i = 0; i < n ; i ++ ) {
  41.                 st.push( _Int() );
  42.         }
  43.  
  44.         while( st.size() ) {
  45.  
  46.                 int x = st.top()-1;st.pop();
  47.                 present[ x ] = 1;
  48.  
  49.                 for(int i = 0; i < n; i ++ ) {
  50.                         if( !present[i] ) continue;
  51.                         G[i][i] = 0;
  52.                         G[i][x] = inp[i][x];
  53.                         G[x][i] = inp[x][i];
  54.                 }
  55.                 int now = 0;
  56.                 for(int i = 0; i < n; i ++ ) {
  57.                         for(int j = 0; j < n; j ++ ) {
  58.                                 G[i][j] = min( G[i][j] , G[i][x]+G[x][j] );
  59.                                 if( G[i][j] < inf ) now += G[i][j];
  60.                         }
  61.                 }
  62.                 Ans.push( now );
  63.         }
  64.         while( Ans.size() ) {
  65.                 printf("%d ", Ans.top() );
  66.                 Ans.pop();
  67.         }
  68.         putchar(10);
  69. }
  70.  
  71. int main()
  72. {
  73.         Main();
  74.         return 0;
  75. }
Success #stdin #stdout 0s 5484KB
comments (?)
stdin
copy 
4
0 57148 51001 13357
71125 0 98369 67226
49388 90852 0 66291
39573 38165 97007 0
2 3 1 4
stdout
copy 
739502 316617 52930 0
https://ideone.com/Sr1E9Z
CF blog post 2
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
secret

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!