Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Problem H:
Sightseeing Tour

  KM city has $N$ sightseeing areas. Currently every pair of area is connected by a bidirectional road.

  However for some reason, Mr. KM, the mayor of this city, decided to make all of these roads one-way . It costs $C_{i, j}$ dollars to renovate the road between area $i$ and area $j$ to a one-way road from area $i$ to area $j$. Of course, Mr. KM is economic and wants to minimize the total cost of the renovation.

  On the other hand, because tourism is the most important industry for KM city, there must exists a tour that goes through all the sightseeing areas, visiting each area exactly once. The first and last area of the path need not to be the same. Can you calculate the minimum total cost required for the renovation, given this situation?
  

  

Input

The first line contains the number of sightseeing area $N$ ($1 \leq N \leq 100$). Next $N$ lines describe the integer matrix $C$, where the $j$-th element of the $i$-th row of the input describes $C_{i,j}$ ($0 \leq C_{i,j} \leq 1,000,000$). For each $i$, you can assume $C_{i,i}$ is always zero.

Output

Output the minimum cost in a line.

Sample Input 1

3
0 2 7
2 0 4
5 8 0

Sample Output 1

11


Sample input:
3
0 2 7
2 0 4
5 8 0


Sample output:
11

Submission status: Wrong Answer

Solution code:
INF = float("inf")
N = int(raw_input())
cost = [map(int,raw_input().split(" ")) for _ in range(N)]
for i in range(N):
	cost[i][i] = INF
dp = [[[INF, []] for _ in range(N)] for _ in range(N-1)]
area = set(range(1,N))
dp[0] = [[v,area - set([idx])]  for idx, v in enumerate(cost[0])]

for i in range(N-1):
	for j in range(1,N):
		for next in dp[i][j][1]:
			tmpv = dp[i][j][0] + cost[j][next]
			if tmpv < dp[i+1][next][0]:
				dp[i+1][next] = [tmpv, dp[i][j][1] - set([next])]

for i in range(1,N):
	dp[N-2][i][0] += cost[i][0]
print min(dp[N-2])[0]

Submission status: Wrong Answer

Solution code:
INF = float("inf")
N = int(raw_input())
cost = [map(int,raw_input().split(" ")) for _ in range(N)]
for i in range(N):
	cost[i][i] = INF
all_area = 2 ** N - 1
dp = {1:[0,0]}
for i in range(N-1):
	tmp_dp = dict()
	for went, (now, v) in dp.iteritems():
		for next in range(1,N):
			bit = 1<<next
			if went & bit != 0 : continue
			tmp = went | bit
			if not (tmp in tmp_dp and tmp_dp[tmp][1] <= v + cost[now][next]):
				tmp_dp[tmp] = [next, v + cost[now][next]]
	dp = tmp_dp

print dp[all_area][1] + cost[dp[all_area][0]][0]

Submission status: Wrong Answer

Solution code:
from math import log
INF = float("inf")
N = int(raw_input())
cost = [map(int,raw_input().split(" ")) for _ in range(N)]
for i in range(N):
	cost[i][i] = INF
all_area = 2 ** N - 1
dp = {1:[0,0]}
for i in range(N-2):
	tmp_dp = dict()
	for went, (now, v) in dp.iteritems():
		for next in range(1,N):
			bit = 1<<next
			if went & bit != 0 : continue
			tmp = went | bit
			if not (tmp in tmp_dp and tmp_dp[tmp][1] <= v + cost[now][next]):
				tmp_dp[tmp] = [next, v + cost[now][next]]
	dp = tmp_dp

print min([v+cost[now][int(log(went^all_area,2))]+cost[int(log(went^all_area,2))][0] for went, (now, v) in dp.iteritems()])

Submission status: Wrong Answer

Solution code:
INF = float("inf")
N = int(raw_input())
cost = [map(int,raw_input().split(" ")) for _ in range(N)]
for i in range(N):
	cost[i][i] = INF
all_area = 2 ** N - 1
dp = {0:[0,0]}
for i in range(N):
	tmp_dp = dict()
	for went, (now, v) in dp.iteritems():
		for next in range(0,N):
			bit = 1<<next
			if went & bit != 0 : continue
			tmp = went | bit
			if not (tmp in tmp_dp and tmp_dp[tmp][1] <= v + cost[now][next]):
				tmp_dp[tmp] = [next, v + cost[now][next]]
	dp = tmp_dp
print dp[all_area][1]

Submission status: Wrong Answer

Solution code:
N = int(raw_input())
cost = [map(int,raw_input().split(" ")) for _ in range(N)]
all_area = 2 ** N - 1
min_cost = [0 for i in range(N)]
for start in range(N):
	dp = {0:[start,start,0]}
	for i in range(N):
		tmp_dp = dict()
		for went, (now, before, v) in dp.iteritems():
			for next in range(N):
				bit = 1<<next
				if went & bit != 0 or next == now or next == before: continue
				tmp = went | bit
				if not (tmp in tmp_dp and tmp_dp[tmp][2] <= v + cost[now][next]):
					tmp_dp[tmp] = [next, now, v + cost[now][next]]
		dp = tmp_dp
	min_cost[start] = dp[all_area][2]
print min(min_cost)

Submission status: Accepted

Solution code:
N = int(raw_input())
C = [map(int,raw_input().split()) for i in xrange(N)]
ans = 0
for i in xrange(N):
    for j in xrange(i+1,N):
        ans += min(C[i][j], C[j][i])
print ans

Submission status: Accepted

Solution code:
N = int(raw_input())
cost = [map(int,raw_input().split(" ")) for _ in range(N)]
all_cost = 0
for i in range(N):
	for j in range(i):
		all_cost += cost[i][j] if cost[i][j] <= cost[j][i] else cost[j][i]
print all_cost

Submission status: Accepted

Solution code:
import sys

def main():
    n = int(input())
    edges = []
    for i in range(n):
        edges.append( list(map(int, sys.stdin.readline().split())) )
    
    # ?±?????????????????????????????????°??????
    # ????????????????????°?????????????????????????????????????????¨????????????
    # ??????????????????????????¨????¨?????????????????????§????´?????°???????????????????????????°??????

    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            ans += min(edges[i][j], edges[j][i])

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n = I()
        a = [LI() for _ in range(n)]
        r = 0
        for i in range(n):
            for j in range(i+1,n):
                r += min(a[i][j], a[j][i])

        rr.append(r)
        break

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
N=input()
C=[map(int,raw_input().split()) for i in range(N)]
s=0
for i in range(N):
    for j in range(i):
        s+=min(C[i][j],C[j][i])
print s

Submission status: Accepted

Solution code:
n = int(input())
graph = [[0 for i in range(n)] for i in range(n)]
for i in range(n):
  graph[i] = list(map(int, input().split()))
ans = 0
for i in range(n):
  for j in range(i+1, n):
    ans += min(graph[i][j], graph[j][i])
print(ans)