package main import ( "bufio" "errors" "fmt" "io" "math" "os" "strconv" ) /********** I/O usage **********/ //str := ReadString() //i := ReadInt() //X := ReadIntSlice(n) //S := ReadRuneSlice() //a := ReadFloat64() //A := ReadFloat64Slice(n) //str := ZeroPaddingRuneSlice(num, 32) //str := PrintIntsLine(X...) /*******************************************************************/ const MOD = 1000000000 + 7 const ALPHABET_NUM = 26 const INF_INT64 = math.MaxInt64 const INF_BIT60 = 1 << 60 var n, m int var A, B, C []int var adjMatrix [16][16]int var dp [1 << 16][16]int var flags [1 << 16][16]bool func main() { n, m = ReadInt(), ReadInt() A, B, C = make([]int, m), make([]int, m), make([]int, m) for i := 0; i < m; i++ { A[i], B[i], C[i] = ReadInt()-1, ReadInt()-1, ReadInt() adjMatrix[A[i]][B[i]] = C[i] adjMatrix[B[i]][A[i]] = C[i] } for S := 0; S < (1 << uint(n)); S++ { for j := 0; j < n; j++ { if S == 0 { flags[S|(1< 0 && flags[S][k] { dist := adjMatrix[k][j] ChMax(&dp[S|(1< target { *updatedValue = target return true } return false } // ChMax accepts a pointer of integer and a target value. // If target value is LARGER than the first argument, // then the first argument will be updated by the second argument. func ChMax(updatedValue *int, target int) bool { if *updatedValue < target { *updatedValue = target return true } return false } // NthBit returns nth bit value of an argument. // n starts from 0. func NthBit(num, nth int) int { return num >> uint(nth) & 1 } // OnBit returns the integer that has nth ON bit. // If an argument has nth ON bit, OnBit returns the argument. func OnBit(num, nth int) int { return num | (1 << uint(nth)) } // OffBit returns the integer that has nth OFF bit. // If an argument has nth OFF bit, OffBit returns the argument. func OffBit(num, nth int) int { return num & ^(1 << uint(nth)) } // PopCount returns the number of ON bit of an argument. func PopCount(num int) int { res := 0 for i := 0; i < 70; i++ { if ((num >> uint(i)) & 1) == 1 { res++ } } return res } /*********** Arithmetic ***********/ // Max returns the max integer among input set. // This function needs at least 1 argument (no argument causes panic). func Max(integers ...int) int { m := integers[0] for i, integer := range integers { if i == 0 { continue } if m < integer { m = integer } } return m } // Min returns the min integer among input set. // This function needs at least 1 argument (no argument causes panic). func Min(integers ...int) int { m := integers[0] for i, integer := range integers { if i == 0 { continue } if m > integer { m = integer } } return m } // DigitSum returns digit sum of a decimal number. // DigitSum only accept a positive integer. func DigitSum(n int) int { if n < 0 { return -1 } res := 0 for n > 0 { res += n % 10 n /= 10 } return res } // Sum returns multiple integers sum. func Sum(integers ...int) int { s := 0 for _, i := range integers { s += i } return s } // CeilInt returns the minimum integer larger than or equal to float(a/b). func CeilInt(a, b int) int { res := a / b if a%b > 0 { res++ } return res } // FloorInt returns the maximum integer smaller than or equal to float(a/b) func FloorInt(a, b int) int { res := a / b return res } // PowInt is integer version of math.Pow // PowInt calculate a power by Binary Power (二分累乗法(O(log e))). func PowInt(a, e int) int { if a < 0 || e < 0 { panic(errors.New("[argument error]: PowInt does not accept negative integers")) } if e == 0 { return 1 } if e%2 == 0 { halfE := e / 2 half := PowInt(a, halfE) return half * half } return a * PowInt(a, e-1) } // AbsInt is integer version of math.Abs func AbsInt(a int) int { if a < 0 { return -a } return a } // Gcd returns the Greatest Common Divisor of two natural numbers. // Gcd only accepts two natural numbers (a, b >= 1). // 0 or negative number causes panic. // Gcd uses the Euclidean Algorithm. func Gcd(a, b int) int { if a <= 0 || b <= 0 { panic(errors.New("[argument error]: Gcd only accepts two NATURAL numbers")) } if a < b { a, b = b, a } // Euclidean Algorithm for b > 0 { div := a % b a, b = b, div } return a } // Lcm returns the Least Common Multiple of two natural numbers. // Lcd only accepts two natural numbers (a, b >= 1). // 0 or negative number causes panic. // Lcd uses the Euclidean Algorithm indirectly. func Lcm(a, b int) int { if a <= 0 || b <= 0 { panic(errors.New("[argument error]: Gcd only accepts two NATURAL numbers")) } // a = a'*gcd, b = b'*gcd, a*b = a'*b'*gcd^2 // a' and b' are relatively prime numbers // gcd consists of prime numbers, that are included in a and b gcd := Gcd(a, b) // not (a * b / gcd), because of reducing a probability of overflow return (a / gcd) * b } // Strtoi is a wrapper of `strconv.Atoi()`. // If `strconv.Atoi()` returns an error, Strtoi calls panic. func Strtoi(s string) int { if i, err := strconv.Atoi(s); err != nil { panic(errors.New("[argument error]: Strtoi only accepts integer string")) } else { return i } } // PrintIntsLine returns integers string delimited by a space. func PrintIntsLine(A ...int) string { res := []rune{} for i := 0; i < len(A); i++ { str := strconv.Itoa(A[i]) res = append(res, []rune(str)...) if i != len(A)-1 { res = append(res, ' ') } } return string(res) }