poj 1062 昂贵的聘礼（最短路 dijk+枚举）

终于A 了，这题做着真麻烦

题目：http://poj.org/problem?id=1062

dijk 一般用于正权有向图

此题的关键在于等级限制的处理，最好的办法是采用枚举，即假设酋长等级为5，等级限制为2，那么需要枚举等级从3~5,4~6,5~7

题意就不用说了，做poj以来的第一道中文题目。

要考虑间接身份差异不可行的情况

如：1 4
10000 3 2
2 1
3 3
1000 2 2
4 1
3 1
1000 3 1
4 2
100 4 0
错误程序出104,答案105。

对于这组数据错误的程序是4->3->2->1的，但4和2不能并存

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cstdlib>
  5 #include<stack>
  6 #include<queue>
  7 #include<cmath>
  8 #include<algorithm>
  9 using namespace std;
 10 
 11 int lim[200];
 12 const int INF=1<<28;
 13 int n;
 14 struct no
 15 {
 16     int p,l,x,a[150],b[150];
 17 } thing[200];
 18 
 19 struct node
 20 {
 21     int u,v,w,next;
 22 } edge[20000];
 23 int head[200],dis[200],cnt;
 24 void add(int u,int v,int w)
 25 {
 26     edge[cnt].u=u;
 27     edge[cnt].v=v;
 28     edge[cnt].w=w;
 29     edge[cnt].next=head[u];
 30     head[u]=cnt++;
 31 }
 32 
 33 int dijkstra(int s)
 34 {
 35     int vis[200],i,j,min;
 36     for(i=1; i<=n; i++)
 37         dis[i]=INF;
 38     memset(vis,0,sizeof(vis));
 39     dis[s]=0;
 40     for(i=1; i<=n; i++)
 41     {
 42         int minn=INF;
 43         int u=s;
 44         for(j=1; j<=n; j++)
 45         {
 46             if(!vis[j] && minn>dis[j] &&lim[j]) //lim标记是否在限制条件内
 47             {
 48                 minn=dis[j];
 49                 u=j;
 50             }
 51         }
 52         for(j=head[u]; j!=-1; j=edge[j].next)
 53         {
 54             int v=edge[j].v;
 55             int newdis=minn+edge[j].w;
 56             if(!vis[v] && newdis < dis[v] && lim[v])//lim标记是否在限制条件内
 57                 dis[v]= newdis;
 58         }
 59         vis[u]=1;
 60     }
 61     min=thing[1].p;
 62     for(i=2; i<=n; i++) //一组完成后 比较
 63     {
 64         if(dis[i]+thing[i].p<min)
 65         min=dis[i]+thing[i].p;
 66     }
 67     return min;
 68 }
 69 int main()
 70 {
 71     int m,i,j,ans;
 72     scanf("%d%d",&m,&n);
 73     cnt=0;
 74     memset(head,-1,sizeof(head));
 75     for(i=1; i<=n; i++)
 76     {
 77         scanf("%d%d%d",&thing[i].p,&thing[i].l,&thing[i].x);
 78         for(j=1; j<=thing[i].x; j++)
 79         {
 80             scanf("%d%d",&thing[i].a[j],&thing[i].b[j]);
 81         }
 82     }
 83     for(i = 1; i <= n; i++)  //其实我这一步没什么必要，当时想少了，下一步就可以搞定
 84     {
 85         for(j=1; j<=thing[i].x; j++)
 86         {
 87             if(abs(thing[i].l-thing[thing[i].a[j]].l)<=m)
 88                 add(i,thing[i].a[j],thing[i].b[j]);//倒着建的图
 89         }
 90     }
 91     ans=thing[1].p;
 92     for(i=m; i>=0; i--)
 93     {
 94         memset(lim,0,sizeof(lim));
 95         for(j=1; j<=n; j++)  //枚举
 96             {
 97                 if(thing[j].l>=(thing[1].l-i)&&thing[j].l<=(thing[1].l+m-i))
 98                 lim[j]=1;
 99             }
100         if(dijkstra(1)<ans)
101             ans=dijkstra(1);
102     }
103     printf("%d
",ans);
104     return 0;
105 }