Untitled
plain_text
a month ago
2.6 kB
0
Indexable
Never
package test; import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static int n, m, k, j; static double[][] a = new double[305][305]; static double[] vs = new double[305]; static int[] vt = new int[305]; static double res1, res2; static int idx1, idx2; public static void main(String[] args) throws FileNotFoundException { //Scanner sc = new Scanner(System.in); Scanner sc = new Scanner(new File("/home/toannv/bss/java/test/src/input.txt")); int T = 1; for(int t=1; t<=T; t++){ n = sc.nextInt(); m = sc.nextInt(); k = sc.nextInt(); j = sc.nextInt(); k = j-k; // if(k%10==0){ // k/=10+1; // }else{ // k =k/10+1; // } // if(j%10==0){ // j/=10+1; // }else{ // j =j/10; // } for(int i=0; i<=n; i++) { vs[i]=0; for(int j=0; j<=n; j++) { a[i][j]=0; } } for(int i=0; i<m; i++){ int xx = sc.nextInt(); int yy = sc.nextInt(); double dept = sc.nextDouble(); a[xx][yy] = dept; } System.out.println(k+" "+j); for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ System.out.print(a[i][j]+" "); } System.out.println(); } idx1=0; idx2=0; res1=0; res2=0; if(k<10) { idx1=1; res1=1; } if(j<10) { idx2=1; res2=1; } BFS(); // System.out.println(idx1 + " " + res1 + " " + idx2 + " " + res2); System.out.format("#%d %d %.6f %d %.6f\n", t, idx2, res2, idx1, res1); } } static void BFS(){ int[] q = new int[205]; int l=0, r=0; q[r++]=1; vs[1]=1; vt[1]=0; int cnt=0; while(l<r){ int top = q[l++]; double vl = vs[top]; int turn = vt[top]+10; if(turn==j+20) break; System.out.println("top" + top + " " + vl); double max = 0; int idx=-1; for(int i=1; i<=n; i++){ if(a[top][i]>0){ System.out.println(i+ " a top: "+a[top][i]); if(vt[i]==turn){ vs[i] = vs[i] + vl*a[top][i]; }else { vs[i] = vl*a[top][i]; q[r++]=i; } vt[i]=turn; System.out.println("vs "+vs[i]); if(vs[i]>max){ max=vs[i]; idx=i; } } } if(idx!=-1){ System.out.println("turn: "+turn); if(k>=turn && k<turn+10) { if(max>res1) { res1 = max; idx1 = idx; } } if(j>=turn && j<turn+10) { if(max>res2) { res2 = max; idx2 = idx; } } } printVS(); System.err.println(max+" "+idx); } } static void printVS(){ System.out.println(); for(int i=1; i<=n; i++){ System.out.print(vs[i]+" "); } System.out.println(); } }