package line;
import java.util.HashMap;
public class pro {
int number;
int[] a_line=new int[10000];
int[] b_line=new int[10000];
int[] d_line=new int[10000];
int number_line;
int s;
String[] name=new String[60];
HashMap<String,Integer> map = new HashMap<String,Integer>();
int[] trip=new int[100];
int number_trip;
public static void main(String[] args) {
pro test=new pro();
}
pro(){
catchline sub=new catchline();
sub.makedata();
a_line=sub.a_line;
b_line=sub.b_line;
d_line=sub.d_line;
name=sub.name;
number_line=sub.number_line;
number=47;
for(s=1;s<number_line+1;s++){
String str=a_line[s]+"to"+b_line[s];
map.put(str,s);
}
int k;
for(k=1;k<30001;k++){
number_trip=1;
trip[1]=fast();
int mode;
mode=0;
while(mode<50){
int tr=search_trip(trip[number_trip]);
int ch=check_trip(tr);
if(ch<50)number_trip=number_trip+1;
if(ch<50)trip[number_trip]=tr;
if(ch>60)mode=100;
}
int s1,s2;
for(s1=1;s1<number_trip;s1++){
for(s2=s1+1;s2<number_trip+1;s2++){
int x1=trip[s1];
int x2=trip[s2];
int p1=point_line(x1,x2);
if(p1<1)number_line=number_line+1;
if(p1<1)a_line[number_line]=x1;
if(p1<1)b_line[number_line]=x2;
if(p1<1)d_line[number_line]=met_line(s1,s2);
String strx=x1+"to"+x2;
if(p1<1)map.put(strx, number_line);
}}
for(s1=1;s1<number_trip;s1++){
for(s2=s1+1;s2<number_trip+1;s2++){
int x1=trip[s1];
int x2=trip[s2];
int p1=point_line(x1,x2);
int d1=d_line[p1];
int d2=met_line(s1,s2);
if(d1>d2)d_line[p1]=d2;
}}
}
int sx,p;
s=40;
sx=47;
p=point_line(s,sx);
System.out.println(name[s]+","+name[sx]+","+d_line[p]);
}
int met_line(int s1,int s2){
int m1,d2;
int s;
d2=0;
for(s=s1;s<s2;s++){
m1=point_line(trip[s],trip[s+1]);
d2=d_line[m1]+d2;
}
return d2;
}
int point_line(int x1,int x2){
String str=x1+"to"+x2;
int px=0;
if(map.containsKey(str))px=map.get(str);
str=x2+"to"+x1;
if(map.containsKey(str))px=map.get(str);
return px;
}
int check_trip(int delta){
int s,ch;
ch=0;
for(s=1;s<number_trip+1;s++){
if(trip[s]==delta)ch=100;
}
return ch;
}
int search_trip(int delta){
int sx,h,s;
int[] z=new int[5000];
s=0;
for(sx=1;sx<number_line+1;sx++){
if(a_line[sx]==delta)s=s+1;
if(a_line[sx]==delta)z[s]=b_line[sx];
}
for(sx=1;sx<number_line+1;sx++){
if(b_line[sx]==delta)s=s+1;
if(b_line[sx]==delta)z[s]=a_line[sx];
}
double m1=s*Math.random();
int m2=(int)(Math.floor(m1)+1);
return z[m2];
}
int fast(){
double n1=number*Math.random();
int n2=(int)(Math.floor(n1))+1;
return n2;
}
}
package line;
import tool.*;
public class catchline {
int s,datanumber;
String[] data=new String[500];
String[] name=new String[500];
String[][] link=new String[500][40];
int[][] code_link=new int[500][40];
int[] number_link=new int[67];
int[] a_line=new int[6700];
int[] b_line=new int[6700];
int[] d_line=new int[6700];
int number_line;
void makedata(){
readfile sub=new readfile();
sub.makedata("data.txt","SJIS");
data=sub.data;
datanumber=sub.datanumber;
int sx;
for(s=1;s<datanumber+1;s++){
String[] x=data[s].split(",");
name[s]=x[1];
for(sx=2;sx<x.length;sx++){
link[s][sx-1]=x[sx];
}
number_link[s]=x.length-2;
}
int tx;
for(s=1;s<datanumber+1;s++){
for(sx=1;sx<number_link[s]+1;sx++){
for(tx=1;tx<48;tx++){
if(link[s][sx].equals(name[tx]))code_link[s][sx]=tx;
}
}}
tx=0;
for(s=1;s<datanumber+1;s++){
for(sx=1;sx<number_link[s]+1;sx++){
tx=tx+1;
a_line[tx]=s;
b_line[tx]=code_link[s][sx];
d_line[tx]=1;
}}
number_line=tx;
}
}
1,北海道,青森県,,
2,青森県,岩手県,,
3,岩手県,宮城県,,
4,宮城県,山形県,,
5,秋田県,山形県,,
6,山形県,宮城県,,
7,福島県,宮城県,,
8,茨城県,福島県,東京都,
9,栃木県,埼玉県,,
10,群馬県,埼玉県,,
11,埼玉県,東京都,,
12,千葉県,東京都,,
13,東京都,神奈川県,,
14,神奈川県,静岡県,,
15,新潟県,群馬県,,
16,富山県,新潟県,,
17,石川県,富山県,,
18,福井県,石川県,,
19,山梨県,東京都,,
20,長野県,山梨県,,
21,岐阜県,滋賀県,,
22,静岡県,愛知県,,
23,愛知県,岐阜県,,
24,三重県,愛知県,,
25,滋賀県,京都府,福井県,
26,京都府,大阪府,,
27,大阪府,兵庫県,,
28,兵庫県,岡山県,,
29,奈良県,大阪府,,
30,和歌山県,大阪府,,
31,鳥取県,兵庫県,,
32,島根県,鳥取県,山口県,
33,岡山県,広島県,,
34,広島県,山口県,,
35,山口県,福岡県,,
36,徳島県,香川県,,
37,香川県,岡山県,,
38,愛媛県,香川県,,
39,高知県,徳島県,愛媛県,
40,福岡県,熊本県,,
41,佐賀県,福岡県,,
42,長崎県,佐賀県,,
43,熊本県,鹿児島県,,
44,大分県,福岡県,,
45,宮崎県,大分県,鹿児島県,
46,鹿児島県,沖縄県,,
47,沖縄県,,,
最終更新：2015年05月06日 09:12
