import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner in=new Scanner(System.in); while(in.hasNext()) { int n=in.nextInt(); int m=in.nextInt(); int k=in.nextInt(); int [][]way=new int[n+1][n+1]; for(int i=0;i<m;i++) { int a=in.nextInt(); int b=in.nextInt(); int l=in.nextInt(); way[a][b]=l; way[b][a]=l; } for(int i=0;i<k;i++) { int start=in.nextInt(); int end=in.nextInt(); System.out.println(dfs(way,start,end,0)); } } } public static int dfs(int[][]way,int start,int end,int len) { int min=Integer.MAX_VALUE; if(start==end) { return len; }else { int result=0; for(int i=1;i<way[start].length;i++) { if(way[start][i]==0) { continue; }else { int l=way[start][i]; way[start][i]=0; way[i][start]=0; result=dfs(way,i,end,l+len); way[start][i]=l; way[i][start]=l; if(min>result) { min=result; } } } return min; } } } |
Double click to view unformatted code.