題意：
N個點(diǎn)，M個邊，每個邊有個標(biāo)號，定義一條路徑和為所有這條路徑上邊的GCD，求從1到2所有路徑的LCM
解法：
BFS，狀態(tài)修正下，用{未節(jié)點(diǎn)，子路徑的GCD}，這樣總狀態(tài)50000，GCD的解法用歐幾里得，LCM=a*b/gcd(a,b)，注意高精度，我偷懶用了java。。。
代碼：
1 import java.util.*;
2 import java.math.*;
3 public class Main {
4
5 /**
6 * @param args
7 */
8 static class pair
9 {
10 int a,b;
11 pair(int aa,int bb)
12 {
13 a=aa;
14 b=bb;
15 }
16 }
17 static int gcd(int a,int b)
18 {
19 while(b!=0)
20 {
21 int t=a%b;
22 a=b;
23 b=t;
24 }
25 return a;
26 }
27 static BigInteger gcd(BigInteger a,BigInteger b)
28 {
29 while(!b.equals(BigInteger.ZERO))
30 {
31 BigInteger t=a.mod(b);
32 a=b;
33 b=t;
34 }
35 return a;
36 }
37 public static void main(String[] args) {
38 Scanner in=new Scanner(System.in);
39 int n=in.nextInt();
40 int map[][]=new int[n][n];
41 boolean used[][]=new boolean[26][2005];
42 LinkedList<pair> q=new LinkedList<pair>();
43 for(int i=0;i<n;i++)
44 for(int j=0;j<n;j++)
45 map[i][j]=in.nextInt();
46 BigInteger lcm=BigInteger.ONE;
47 BigInteger tmp[]=new BigInteger[2005];
48 tmp[1]=BigInteger.ONE;
49 for(int i=2;i<tmp.length;i++)
50 tmp[i]=tmp[i-1].add(BigInteger.ONE);
51 for(int i=0;i<26;i++)
52 Arrays.fill(used[i], false);
53 for(int i=0;i<n;i++)
54 if(map[0][i]!=0)
55 {
56 used[i][map[0][i]]=used[0][map[0][i]]=true;
57 q.add(new pair(i,map[0][i]));
58 }
59 while(!q.isEmpty())
60 {
61 pair top=q.pollFirst();
62 //System.out.println(top.a+" "+top.b);
63 if(top.a==1)
64 {
65 BigInteger t=tmp[top.b].multiply(lcm);
66 t=t.divide(gcd(lcm.add(BigInteger.ZERO),tmp[top.b].add(BigInteger.ZERO)));
67 lcm=t;
68 continue;
69 }
70 for(int i=0;i<n;i++)
71 if(map[top.a][i]!=0&&!used[i][gcd(top.b,map[top.a][i])])
72 {
73 used[i][gcd(top.b,map[top.a][i])]=true;
74 q.add(new pair(i,gcd(top.b,map[top.a][i])));
75 }
76 }
77 System.out.println(lcm);
78
79 }
80
81 }