首页 > 代码库 > poj 1062 昂贵的聘礼 最短路

poj 1062 昂贵的聘礼 最短路

2024-07-17 20:19:31   216人阅读

 

          中文题 题意就不说了，注意题目里说的是所有的人等级差不能超过一个值，而不是两个两个之间不能超过（这里题意搞错了wa半天），

 建好图，枚举可以在这个最短路里的最高级和最低级再跑最短路 得到最小值就可以了。

 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 #define INF 99999999 7 struct node{int price,rank1;}p[1002]; 8 int g[102][102],d[102]; 9 bool vis[102];10 11 int dij(int s,int n,int min1,int max1)12 {13     int minn,mini;14     for(int i=1;i<=n;i++)15         d[i]=INF;16     memset(vis,false,sizeof(vis));17     d[s]=0;18     for(int k=1;k<n;k++)19     {20         minn=INF;21         for(int i=1;i<=n;i++)22             if(!vis[i]&&d[i]<minn)23             {24                 minn=d[i];25                 mini=i;26             }27         vis[mini]=true;28         for(int i=1;i<=n;i++)29             if(p[i].rank1>=min1&&p[i].rank1<=max1&&d[mini]+g[mini][i]<d[i])30                 d[i]=d[mini]+g[mini][i];31     }32     minn=INF;33     for(int i=1;i<=n;i++)34     {35         d[i]+=p[i].price;36         if(minn>d[i])37             minn=d[i];38     }39     return minn;40 }41 42 int main()43 {44     int n,k,c,a,b;45     while(~scanf("%d%d",&c,&n))46     {47         for(int i=0;i<=n;i++)48             for(int j=0;j<=n;j++)49                g[i][j]=INF;50         for(int i=1;i<=n;i++)51         {52            scanf("%d%d%d",&p[i].price,&p[i].rank1,&k);53            while(k--)54            {55                scanf("%d%d",&a,&b);56                g[i][a]=min(b,g[i][a]);57            }58         }59         int temp,ans=INF;60         temp=p[1].rank1;61         temp=max(p[1].rank1-c,0);62         for(int i=temp;i<=p[1].rank1;i++)63         {64             int pp;65             pp=dij(1,n,i,i+c);66             if(pp<ans)67                 ans=pp;68         }69         printf("%d\n",ans);70     }71 }

 


联系
我们