Part7.13ダイナミックプログラミング(Dynamic Programming)抽選(Floyd-Warshallアプリケーション)

質問する

!

入力

入力した最初の行には会員数があります.
ただし、会員数は50名を超えない.2行目以降、1行に2つの会員番号があり、
これは2人の会員が互いに友达であることを示している.会員番号は1から、会員数によって番号が貼ってあります.
最後の行には2つの-1があります

しゅつりょく

1行目は会長候補の点数と会長候補の数を出力し、2行目はすべての会長候補を出力する.
始まりました.

正解を解く

floodアルゴリズム

イニシャル化シナリオ(最初はすべて100)

幹線初期化(直ノード&対角線0)

FloydWarshallアルゴリズム

resレコード

正しいコード

import sys
sys.stdin = open ("input.txt", "rt")

def input():
    return sys.stdin.readline().rstrip()

if __name__ == "__main__":
    #n 은 정점번호, m은 간선의 개수
    n = int(input())

    dis=[[100]*(n+1) for _ in range(n+1)]

    for i in range(1,n+1):
        dis[i][i] = 0 #대각선 0으로 초기화

    while True:
        a, b = map(int,input().split())
        if a==-1 and b == -1:
            break
        dis[a][b] = 1
        dis[b][a] = 1

    for k in range(1,n+1): # 플로이드 워샬 알고리즘
        for i in range(1, n+1):
            for j in range(1, n+1):
                dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]) 

    res=[0]*(n+1)
    score = 100
    for i in range(1, n+1): # 최댓값 max에 저장
        for j in range(1,n+1):
            res[i]= max(res[i], dis[i][j]) #i번 회원의 가까운 정도 최댓값 기록된다.
        score = min(score, res[i])
    out=[]
    for i in range(1, n+1):
        if res[i]==score:
            out.append(i)
    print("%d %d" %(score, len(out)))
    for x in out:
        print(x)

コメント