1062.cpp

这些是我到目前在PKU上做出的题目

#include <stdio.h>
int main()
{
    int M,n,i,j,k,jcost,origin_max=0,distance[101],min_cost,origin[101][101],rank[101],temp,last_rank,vertex,min_distance;
    bool flag[101];
    scanf("%d %d",&M,&n);
    for(i=0;i<=n;i++)
        for(j=0;j<=n;j++)
            origin[i][j]=-1;
    for(i=1;i<=n;i++)
    {
        scanf("%d %d %d",&origin[0][i],&rank[i],&temp);
        for(k=0;k<temp;k++)
        {
            scanf("%d %d",&j,&jcost);
            origin[j][i]=jcost;
        }
    }
    for(i=0;i<=n;i++)
        for(j=0;j<=n;j++)
            if(origin[i][j]>origin_max)
                origin_max=origin[i][j];
     for(i=0;i<=n;i++)
        for(j=0;j<=n;j++)
            if(origin[i][j]==-1)
                origin[i][j]=origin_max+1;

    min_cost=origin_max+1;
    last_rank=rank[1];
    for(i=0;i<=M;i++)
    {
        int copy[101][101];
        for(j=0;j<=n;j++)
            for(k=0;k<=n;k++)
                copy[j][k]=origin[j][k];
        for(j=2;j<=n;j++)
        {
            if(rank[j]<last_rank-M+i||rank[j]>last_rank+i)
                for(k=0;k<=n;k++)
                {
                    copy[j][k]=origin_max+1;
                    copy[k][j]=origin_max+1;
                }
        }
        for(j=0;j<=n;j++)
        {
            flag[j]=false;
            distance[j]=copy[0][j];
        }
        flag[0]=true;
        while(true)
        {
            min_distance=origin_max+1;
            for(j=1;j<=n;j++)
            {
                if(!flag[j]&&distance[j]<min_distance)
                {
                    vertex=j;
                    min_distance=distance[j];
                }
            }	
            if(vertex==1)
            {
                if(min_cost>min_distance)
                    min_cost=min_distance;
                break;
            }
            flag[vertex]=true;
            for(j=1;j<=n;j++)
            {
                if(!flag[j])
                    distance[j]=distance[j]<copy[vertex][j]+distance[vertex]?distance[j]:copy[vertex][j]+distance[vertex];
            }
        }
    }
    printf("%d\n",min_cost);
    return 0;
}