首页 > 代码库 > poj1062-昂贵的聘礼
poj1062-昂贵的聘礼
题目链接 这里
解题思路
中文题，终于不用翻译了。。。
把优惠的物品看成节点，要交的钱看为边权
学到一个技巧：把edge[0][]存每个物品的初始价值
这样求最短路逻辑就比较畅通了。。。
如果你的边是从低阶层指到高阶层，那要枚举最高阶层
如果你的边是从高阶层指向底阶层，那要枚举最底阶层
要不然你就都枚举好了。。。
代码
#include<iostream>#include<cstdlib>#include<string.h>using namespace std;const int MAX_SIZE = 110;struct node { int value; //直接交易的价格 int order; //地位}v[MAX_SIZE]; //顶点集合bool vis[MAX_SIZE];int edge[MAX_SIZE][MAX_SIZE]; //边集int q[MAX_SIZE]; //距离int m, n;void read(){ int k; for(int i=1; i<=n; i++) { cin >> v[i].value >> v[i].order >> k; for(int j=0; j<k; j++) { int u; cin >> u; cin >> edge[u][i]; } edge[0][i] = v[i].value; }}int dist(int k){ for(int i=1; i<=n; i++) q[i] = v[i].value; for(int i=1; i<=n; i++) { int minNum = 1e9; int x = k; for(int j=1; j<=n; j++) { if(vis[j]) continue; if(q[j] < minNum) { minNum = q[j]; x = j; } } vis[x] = true; for(int j=1; j<=n; j++) { if(vis[j]) continue; q[j] = min(q[j], q[x] + edge[x][j]); } } return q[1];}int main(){ int mins = 1e9; cin >> m >> n; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) edge[i][j] = 1e9; read(); //读取 for(int i=1; i<=n; i++) { int sum; memset(vis, 0, sizeof(vis)); for(int j=1; j<=n; j++) if(v[j].order > v[i].order || (v[i].order - v[j].order > m)) { vis[j] = true; } sum = dist(i); if(sum < mins) mins = sum; } cout << mins << endl; return 0;}
poj1062-昂贵的聘礼
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。