POJ-1062 昂贵的聘礼---Dijkstra+枚举上界

题目链接：

题目大意：

中文题

思路：

1是终点，可以额外添加一个源点0，0到任意一节点的距离就是这个点的money，最终求的是d[1]最小值，但是由于有等级观念，所以必须枚举，每次枚举等级的上界，如果有不符合当前枚举的上界，就标记其不加入dijk算法中，然后跑一遍最短路，求出d[1]，最终取d[1]的最小值

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<stack>

 #include<map>

 #include<set>

 #include<sstream>

 #define MEM(a, b) memset(a, b, sizeof(a));

 using namespace std;

 typedef long long ll;

 const int maxn =  + ;

 const int INF = 0x3f3f3f3f;

 int T, n, m, cases;//m是等级差

 int Map[maxn][maxn];

 int d[maxn], v[maxn];

 struct node

 {

     int money, rank;

 }cnt[maxn];

 int dijkstra()

 {

     for(int i = ; i <= n; i++)d[i] = cnt[i].money;//假定的原点0，到每个点的距离就是它自己的价格

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

     {

         int x = , m = INF;

         for(int i = ; i <= n; i++)if(!v[i] && m > d[i])m = d[x = i];//找出当前在集合中的最小距离

         if(!x)break;//已经全部标记完毕

         v[x] = ;

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

             if(!v[i])d[i] = min(d[i], d[x] + Map[x][i]);//这里必须加上判断条件，因为有部分物品由于等级限制没有加入选项中

     }

     return d[];

 }

 int main()

 {

     cin >> m >> n;

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

         for(int j = ; j <= n; j++)Map[i][j] = INF;

     MEM(cnt, );

     MEM(v, );

     int x, a, b;

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

     {

         cin >> cnt[i].money >> cnt[i].rank >> x;

         while(x--)

         {

             cin >> a >> b;

             Map[a][i] = b;//存图，存下从a到i的路径，这样就可以转化成求到点1的最短路径

         }

     }

     int ans = INF;

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

     {

         int maxrank = cnt[i].rank;//枚举rank的上界

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

             if(maxrank - cnt[j].rank > m || cnt[j].rank > maxrank)v[j] = ;

             //事先标记好不符合条件的物品，如果有等级大于当前枚举的最大等级或者等级差超过m的标记，在dijk算法中不添加这些元素

             else v[j] = ;

         ans = min(ans, dijkstra());

     }

     cout<<ans<<endl;

     return ;

 }

秒客网

POJ-1062 昂贵的聘礼---Dijkstra+枚举上界

相关文章