首页 > 代码库 > poj 1062 昂贵的聘礼 解题报告

poj 1062 昂贵的聘礼 解题报告

2024-07-16 00:16:10   226人阅读

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

      这一题只要想到如何建图，就不太难解决了。假设对于编号为 i 的物品，如果它得到物品 j 后价格从 pricei 降低到 pricej 的话，就用一个cost[i][j] = pricej。也就是从物品 i 到物品 j 连一条有向边。每一个编号的物品都这样处理，然后套用dijk 算法，求出从每个点出发的最短路，最终最小的那个就是答案。考虑到等级限制，别人可以跟酋长接触的前提是这个人的等级在 [ level 酋长-m  ~ level酋长+m ] 范围内。

       这题可以算得上比较灵活的 最短路。

     

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6  7 const int INF = 1e9; 8 const int N = 100 + 10; 9 int dist[N], vis[N];10 int level[N], cost[N][N];11 int n, m;12 13 int dijkstra(int cost[][N], int p)14 {15     memset(vis, 0, sizeof(vis));16     for (int i = 1; i <= n; i++)17         dist[i] = cost[0][i];18     dist[0] = 0, vis[0] = 1;19     for (int i = 1; i <= n; i++)20     {21         int u;22         int maxx = INF;23         for (int j = 1; j <= n; j++)24         {25             if (dist[j] < maxx && !vis[j])26                 maxx = dist[u=j];27         }28         vis[u] = 1;29         for (int j = 0; j <= n; j++)30         {31             if (!vis[j] && dist[j] > dist[u]+cost[u][j] && level[u] >= p && level[u] <= p+m)32                 dist[j] = dist[u] + cost[u][j];33         }34     }35     return dist[1];36 }37 38 int main()39 {40     while (scanf("%d%d", &m, &n) != EOF)41     {42         int P, L, X;43         int id, price;44         for (int i = 0; i <= n; i++)45         {46             for (int j = 0; j <= n; j++)47                 cost[i][j] = (i == j ? 0 : INF);48         }49         for (int i = 1; i <= n; i++)50         {51             scanf("%d%d%d", &P, &L, &X);52             cost[0][i] = P;53             level[i] = L;54             for (int j = 0; j < X; j++)55             {56                 scanf("%d%d", &id, &price);57                 cost[id][i] = price;58             }59         }60         int ans = INF;61         for (int i = level[1]-m; i <= level[1]; i++)62             ans = min(ans, dijkstra(cost, i));63         printf("%d\n", ans);64     }65     return 0;66 }

 

   


联系
我们