07 - 그림 4 해 리포터 의 시험 (25 점)

제목 출처: 중국 대학 MOOC - 진 월, 하 흠 명 - 데이터 구조 - 2018 봄 작가: 진 월 단위: 절강대학 문제 설명: 해 리포터 가 시험 을 보 려 고 하 는데 그 는 당신 의 도움 이 필요 합 니 다.이 수업 은 저주 로 한 동물 을 다른 동물 로 만 드 는 기술 을 배 웠 다.예 를 들 어 고양 이 를 쥐 로 만 드 는 징 크 스 는 haha, 쥐 를 물고기 로 만 드 는 징 크 스 는 hehe 등 이다.반대 방향 변화의 징 크 스 는 원래 의 징 크 스 를 간단하게 거꾸로 읽 는 것 이다. 예 를 들 어 ah 는 쥐 를 고양이 로 만 들 수 있다.또한 고양 이 를 물고기 로 만 들 려 면 직접 저주 lalala 를 읽 거나 고양이 가 쥐 로 변 하고 쥐 가 물고기 로 변 하 는 징 크 스 를 연결 해서 읽 을 수 있다.현재 해 리포터 의 손 에는 모든 변형 저주 와 변 할 수 있 는 동물 들 이 담 겨 있 는 교재 가 있다.선생님 은 그 가 스스로 동물 한 마 리 를 데 리 고 시험장 에 가 는 것 을 허락 하 셨 는데, 그 가 이 동물 을 임의의 지 정 된 동물 로 만 드 는 능력 을 고찰 해 야 한다.그래서 그 는 당신 에 게 물 었 습 니 다. 어떤 동물 을 데 리 고 가면 가장 변 하기 어 려 운 동물 (즉, 이 동물 이 해 리포터 가 가 져 간 동물 로 변 하 는 데 필요 한 저주 가 가장 깁 니까?) 에 게 필요 한 저주 가 가장 짧 습 니까?예 를 들 어 고양이, 쥐, 물고기 만 있다 면 해 리포터 가 쥐 를 데 리 고 가 야 한다. 쥐 가 다른 두 동물 이 되 려 면 4 글자 만 읽 어야 하기 때문이다.고양 이 를 데 리 고 가면 적어도 6 자 는 읽 어야 고양 이 를 물고기 로 만 들 수 있다.갈치 가 가 는 것 도 최선 이 아니다.입력 형식: 입력 설명: 첫 번 째 줄 에 두 개의 정수 N (≤ 100) 과 M 을 입력 하 십시오. 그 중에서 N 은 시험 과 관련 된 동물 총수 이 고 M 은 직접 변형 에 사용 되 는 저주 수 입 니 다.간단하게 보기 위해 서 우 리 는 동물 을 1 ~ N 번호 로 누 를 것 이다.그 다음 에 M 줄 은 각 줄 에 3 개의 정 수 를 주 었 는데 각각 두 동물 의 번호 와 그들 사이 의 변형 에 필요 한 저주 의 길이 (≤ 100) 이 고 숫자 간 에 빈 칸 으로 구분 되 었 다.출력 형식: 해 리포터 가 시험장 에 가 져 가 는 동물 의 번호 와 가장 긴 변형 주문 의 길 이 를 출력 하고 중간 에 빈 칸 으로 구분 해 야 합 니 다.한 마리 의 동물 만 가지 고 모든 변형 요 구 를 완성 할 수 없다 면 0 을 출력 한다.만약 몇 마리 의 동물 이 모두 선택 할 수 있다 면, 출력 번호 가 가장 작은 그 마리.입력 샘플: 6 11 3 4 70 1 2 1 5 50 2 6 50 6 60 1 3 70 4 6 80 5 1 100 2 4 60 5 80 출력 샘플: 4 70
해답: 이 문 제 는 다 원 최 단 경로 입 니 다. 최대 M 의 테스트 점 이 나타 날 수 있 고 희소 도가 나타 날 수 있 기 때문에 N 차 단원 최 단 경 로 를 사용 하 는 것 이 좋 지 않 습 니 다. 플 로 이 드 알고리즘 을 사용 하 는 것 이 좋 습 니 다.플 로 이 드 로 경로 가중치 행렬 을 업데이트 한 후, 모든 줄 의 최대 치 를 찾 아 접근 할 수 없 는 점 이 있 는 지, 없 으 면 출력 에 저 장 된 가장 짧 은 저주 길이 와 출발점 을 판단 합 니 다.

#include 
#include 
using namespace std;
const int maxn=101;
int G[maxn][maxn];
const int INF=10001;
int N,M;
void floyd()
{
    for(int k=1;k<=N;k++)
    {
        for(int i=1;i<=N;i++)
        {
            for(int j=1;j<=N;j++)
            {
                if(G[i][k]+G[k][j]void findMaxWeight()
{
    int findMinPath=INF;
    int findMinPoint;
    for(int i=1;i<=N;i++)
    {
        int maxNum=0;
        for(int j=1;j<=N;j++)
        {
            if(G[i][j]>maxNum)
            {
                maxNum=G[i][j];
            }
        }
        if(maxNumif(findMinPath==INF)
        cout<<"0";
    else
    {
        cout<" "<int main()
{
    cin>>N>>M;
    fill(G[0],G[0]+maxn*maxn,INF);
    for(int i=1;i<=M;i++)
    {
        int p1,p2,weight;
        cin>>p1>>p2>>weight;
        G[p1][p2]=G[p2][p1]=weight;
    }
    for(int i=1;i<=N;i++)
    {
        G[i][i]=0;
    }
    floyd();
    findMaxWeight();
    return 0;
}