http://poj.org/problem?id=1695 /* @author:zeropinzuo */ import java.io.*; import java.util.*; public class Main{ static Scanner cin; public static void main(String args[]){ cin = new Scanner(System.in); int M = cin.nextInt(); for(int i=0;i< M;i++) run(); } static void run(){ int N = cin.nextInt(); int[][] d = new int[N+1][N+1]; for(int i=1;i< N;i++) for(int j=i+1;j<=N;j++) d[i][j] = cin.nextInt(); int[][][] f = new int[N+1][N+1][N+1]; for(int i=1;i<=N;i++)//��ʼ�� for(int j=1;j<=N;j++) for(int k=1;k<=N;k++) f[i][j][k]=10000; f[1][1][1] = 0; for(int k=2;k<=N;k++) for(int i=1;i< k;i++) for(int j=1;j< k;j++){ if(f[i][j][k1]+d[i][k]< f[j][k1][k]){ f[j][k1][k]=f[i][j][k1]+d[i][k]; f[k1][j][k]=f[i][j][k1]+d[i][k]; } if(f[i][j][k1]+d[j][k]< f[i][k1][k]){ f[i][k1][k]=f[i][j][k1]+d[j][k]; f[k1][i][k]=f[i][j][k1]+d[j][k]; } if(f[i][j][k1]+d[k1][k]< f[i][j][k]){ f[i][j][k]=f[i][j][k1]+d[k1][k]; f[j][i][k]=f[i][j][k1]+d[k1][k]; } } int opt=f[1][1][N]; for(int i=1;i< N;i++) for(int j=1;j< N;j++) if(f[i][j][N]< opt) opt=f[i][j][N]; System.out.println(opt); } }
Meta

Recent Posts
Recent Comments
Archives
 April 2023
 February 2023
 January 2023
 December 2022
 November 2022
 September 2022
 June 2022
 July 2021
 January 2021
 February 2020
 September 2019
 March 2018
 February 2018
 August 2016
 July 2016
 June 2016
 May 2016
 April 2016
 March 2016
 February 2016
 January 2016
 December 2015
 November 2015
 October 2015
 September 2015
 August 2015
 July 2015
 June 2015
 May 2015
 April 2015
 March 2015
 February 2015
 January 2015
 December 2014
 November 2014
 October 2014
 September 2014
 August 2014
 July 2014
 June 2014
 May 2014
 April 2014
 March 2014
 February 2014
 January 2014
 December 2013
 November 2013
 October 2013
 September 2013
 August 2013
 July 2013
 June 2013
 May 2013
 April 2013
 March 2013
 February 2013
 January 2013
 December 2012
 November 2012
 October 2012
 September 2012
 August 2012
 July 2012
 June 2012
 May 2012
 April 2012
 March 2012
 February 2012
 January 2012
 December 2011
 November 2011
 October 2011
 September 2011
 August 2011
 July 2011
 June 2011
 May 2011
 April 2011
 March 2011
 February 2011
 January 2011
 December 2010
 November 2010
 October 2010
 September 2010
 August 2010
 July 2010
 June 2010
 May 2010
 April 2010
 March 2010
 February 2010
 January 2010
 December 2009
 November 2009
 October 2009
 September 2009
 August 2009
 July 2009
 June 2009
 May 2009
 April 2009
 March 2009
 February 2009
Categories