百度笔试编程题

题目一，最短路径，套模板AC40%(目测因为自己用python。。。)

import sys
def FloydWarshall(V_num, weight):
    '''
    :param V_num: int
    :param weight: dict{(v, u):w1, }
    :return:
    '''
    dist = [[sys.maxint for j in range(V_num)] for i in range(V_num)]
    for (u, v) in weight:
        dist[u][v] = weight[(u, v)]
        dist[v][u] = weight[(u, v)]
    for k in range( V_num):
        for i in range( V_num):
            for j in range( V_num):
                if(dist[i][k]<>sys.maxint and dist[k][j]<>sys.maxint and dist[i][k]+dist[k][j]<dist[i][j]):
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

t = int(raw_input())
for tid in range(t):
    n, m, a, b = map(int, raw_input().split())
    s = map(int, raw_input().split())
    e = map(int, raw_input().split())
    weight = {}
    for __ in range(m):
        u, v, w = map(int, raw_input().split())
        weight[(u-1, v-1)] = w
        #weight[(v, u)] = w
    dist = FloydWarshall(n, weight)
    ans = sys.maxint
    for si in s:
        for ei in e:
            ans = min(ans, dist[si-1][ei-1])
    print "Case #"+str(tid+1)+": ",
    if ans==sys.maxint:
        print "No answer"
    else:
        print ans

题目二，子串，hash解之

s = raw_input()
current = None
ans = 0
cnt = 0
visited = {}
for c in s:
    if c==current:
        cnt += 1
        if cnt > visited[c]:
            visited[c] = cnt
            ans += 1
    else:
        current = c
        if c not in visited:
            visited[c] = 1
            ans += 1
        cnt = 1
#print visited
print ans