uva 567 Risk

UVA 는 사실 매우 괴 롭 혔 습 니 다. 제목 이 너무 길 었 습 니 다. 그리고 제목 의 뜻 이 물 과 같 을 수 있 습 니 다. 입 출력 도 이상 하고 세련 된 것 으로 생각 합 니 다.
사실은 가장 짧 은 경로 의 누 드 문제 다.20 개의 점 이 고정 되 어 있 고 입력 은 두 부분 으로 나 뉘 며 앞부분 은 19 줄 이 있 습 니 다. 각 줄 은 n 개의 숫자 가 있 음 을 나타 내 고 n 개의 숫자 를 입력 합 니 다.i 줄 에서 출력 한 숫자 v 는 i 와 v 사이 에 변 이 있 고 방향 이 없 으 며 모든 변 의 가중치 가 1 임 을 나타 낸다.
입력 한 뒷부분 은 먼저 m 를 입력 하여 m 개의 조회 가 있 음 을 나타 낸다. 아래 m 줄 의 입력 점 u, v 출력 두 점 사이 의 가장 짧 은 경로
분명히 플 로 이 알고리즘 의 누 드 문제 다.그런데 spafa 를 새로 배 웠 어 요. spfa 도 올 려 주세요.
주의해 야 할 것 은 20 개의 점 이 1 번 에서 20 번 까지 이지 만 입력 은 19 줄 밖 에 안 됩 니 다. 게다가 출력 형식 도 주의해 야 합 니 다. 본 문 제 는 1Y 입 니 다. 연습 선수 라 고 생각 합 니 다.
 SPFA

//   spafa  

//                 m   

//           spfa，      floy    

//          ，             

//                         spfa

//            ，             

//             ，     ， d        

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

#define N 25  //   20  

#define INF 1000000000

int g[N][N];  //    

int d[N];     //      

bool vis[N];  //           

queue <int> q;

int input()

{

    int n,v;

    for(int i=1; i<=20; i++)

        for(int j=1; j<=20; j++)

            g[i][j]=INF;

    if(scanf("%d",&n)==EOF)  return 0;

    for(int i=1; i<=n; i++)

    {

        scanf("%d",&v);

        g[1][v]=g[v][1]=1;

    }

    for(int i=2; i<=19; i++)

    {

        scanf("%d",&n);

        for(int j=1; j<=n; j++)

        {

            scanf("%d",&v);

            g[i][v]=g[v][i]=1;

        }

    }

/*

    for(int i=1; i<=20; i++)

    {

        for(int j=1; j<=20; j++)

            if(g[i][j]==1) printf("1 ");

            else           printf("* ");

        printf("
");

    }

*/

    return 1;

}



void spfa(int s)  //    s

{

    memset(vis,0,sizeof(vis));

    for(int i=1; i<=20; i++)  d[i]=INF;  //   

    d[s]=0;        //      0

    while(!q.empty()) q.pop();

    q.push(s);  //    

    vis[s]=1;   //          



    while(!q.empty())

    {

        int u;

        u=q.front();  //      

        q.pop();      //      

        vis[u]=0;     //       

        //   u      v       ，      v    ，   v  

        for(int v=1; v<=20; v++)  //        u 

            if( d[u]+g[u][v] < d[v] )  //    d[v]

            {

                d[v]=d[u]+g[u][v];

                if(!vis[v])  // v      

                {

                    q.push(v);  // v  

                    vis[v]=1;   //    

                }

            }

    }

/*

    for(int i=1; i<=20; i++)

        printf("%d ",d[i]);

    printf("
");

*/

    return ;

}



int main()

{

    int T=0;

    while(1)

    {

        if(!input()) break;

        T++;

        int m;

        printf("Test Set #%d
",T);

        scanf("%d",&m);  //  m   

        for(int i=1; i<=m; i++)  //  m   

        {

            int u,v;

            scanf("%d%d",&u,&v);

            spfa(u);

            printf("%2d to %2d: %d
",u,v,d[v]);

        }

        printf("
");

    }

    return 0;

}

Floy

#include <stdio.h>

#include <string.h>

#define INF 1000000000

#define N 25

int d[N][N];



void Floy()

{

    int i,j,k;

    for(k=1; k<=20; k++)

        for(i=1; i<=20; i++)

            for(j=1; j<=20; j++)

                if(d[i][j] > d[i][k]+d[k][j])

                    d[i][j]=d[i][k]+d[k][j];

    return ;

}

int main()

{

    int T=0;

    int i,j,n,m,u,v;

    while(scanf("%d",&n)!=EOF)

    {

        T++;

        for(i=1; i<=20; i++)

            for(j=1; j<=20; j++)

                if(i==j) d[i][j]=0;

                else     d[i][j]=INF;



        for(i=1 ;i<=n; i++)

        {

            scanf("%d",&v);

            d[1][v]=d[v][1]=1;

        }



        for(u=2; u<=19; u++)

        {

            scanf("%d",&n);

            while(n--)

            {

                scanf("%d",&v);

                d[u][v]=d[v][u]=1;

            }

        }



        Floy();

        printf("Test Set #%d
",T);

        scanf("%d",&m);  //m    

        for(i=1; i<=m; i++)

        {

            scanf("%d%d",&u,&v);

            printf("%2d to %2d: %d
",u,v,d[u][v]);

        }



        printf("
");

    }

    return 0;

}