【 도 론 】 bfs, 디 제 스 트 라, 최소 생 성 트 리

1.2139 데이터 구조 실험의 도 론 5: 시작 점 에서 목표 점 까지 의 최 단 걸음 수 (BFS)
단 방향, 출력 최소 필요 단계

#include 
#include 
#include 
int a[1003][1003],v[1003],n;
struct node
{
    int data;
    int step;
}x,t;
void bfs(int n)
{
    int i,in=0,out=0;
    struct node q[1003];
    v[n]=1;
    t.data=n;
    t.step=0;
    q[in++]=t;
    while(in>out)
    {
        x=q[out++];
        if(x.data==1)
        {
            printf("%d
",x.step);
            return ;
        }
        for(i=1;i<=n;i++)
        {
            if(a[x.data][i]==1&&v[i]==0)
            {
                t.data=i;
                t.step=x.step+1;
                q[in++]=t;
                v[i]=1;
            }
        }
    }
    printf("NO
");
    return ;
}
int main()
{
    int t,m,x,y,s;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(a,0,sizeof(a));
        memset(v,0,sizeof(v));
        while(m--)
        {
            scanf("%d%d",&x,&y);
            a[x][y]=1;
        }
        bfs(n);
    }
    return 0;
}

2.3363 데이터 구조 실험의 도 론 7: 당나귀 친구 계획
디 제 스 트 라

#include 
#include 
#include 
#define MAX 0x3f3f3f3f
int map[505][505],money[505][505],v[505],d[505],mon[505];
void dij(int n,int s)
{
    int j,k,i,min;
    for(i=1;i<=n;i++)
    {
        d[i]=map[s][i];
        mon[i]=money[s][i];
    }
    v[s]=1;
    d[s]=0;
    mon[s]=0;
    for(i=1;id[k]+map[k][j])
                {
                    d[j]=d[k]+map[k][j];
                    mon[j]=mon[k]+money[k][j];
                }
                else if(d[j]==d[k]+map[k][j]&&mon[j]>mon[k]+money[k][j])
                {
                    mon[j]=mon[k]+money[k][j];
                }
            }
        }
    }
}
int main()
{
    int t,n,m,price,s,e,l,x,y,i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d",&n,&m,&s,&e);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(i==j)
                    map[i][j]=0;
                else
                    map[i][j]=MAX;
            }
        }
        while(m--)
        {
            scanf("%d%d%d%d",&x,&y,&l,&price);
            map[x][y]=map[y][x]=l;
            money[x][y]=money[y][x]=price;
        }
        memset(v,0,sizeof(v));
        dij(n,s);
        printf("%d %d
",d[e],mon[e]);
    }
    return 0;
}

3.SDUT 2144 데이터 구조 실험의 도 론 9: 최소 생 성 트 리
n 개 도시 가 있 는데 그 중에서 일부 도시 간 에 도 로 를 건설 할 수 있 고 서로 다른 도 로 를 건설 하 는 비용 은 다르다.지금 우 리 는 최소한 얼마의 돈 을 써 서 도 로 를 건설 하면 모든 도 시 를 한데 연결 시 켜 임의의 도시 에서 출발 하여 다른 임의의 도시 에 도착 할 수 있 는 지 알 고 싶다.
도시 개 수 를 건설 할 수 있 는 도로 개 수 를 제시 하 다.(n < = 100, m < = 10000), 몇 개의 abc 의 값 을 제시 하여 도시 a 와 도시 b 사이 에 도 로 를 건설 할 수 있 고 대 가 는 c 입 니 다.수출 최소 비용. 

#include 
#include 
#include 
struct node
{
    int a,b,c;
} mp[10002];
int f[100005];
int gett(int x)//  
{
    if(f[x]==x)
        return x;
    f[x]=gett(f[x]);
    return f[x];
}
int merge(int x,int y)//       ，              
{
    int a=gett(x),b=gett(y);
    if(a!=b)
    {
        f[a]=b;
        return 0;
    }
    else return 1;
}
void pai(int l,int r)
{
    int i=l,j=r;
    struct node k=mp[l];
    if(l>=r)
        return ;
    while(i=k.c)j--;
        mp[i]=mp[j];
        while(i