题目类型 Dijkstra算法的运用
题目意思
中文题目描述
解题方法
先枚举地位的范围(因为第１件物品必须在交易中出现所以范围区间的左端点就是 L1-m -> L1 右端点范围是 L1 -> L1+m)
确定范围后就是类似Dijkstra算法的贪心过程
d[i] 表示交易终点停在第 i 个物品时总共所需的花费 那么每次取最小的 d[i] 去更新其他的 d[] 即可
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int INF = 1<<29;
const int maxn = 100 + 10;
struct Node {
int p, l, x;
}node[maxn];
struct PNode {
int d, u;
PNode(int d, int u) : d(d), u(u) {}
PNode(){}
bool operator < (const PNode & rhs) const {
return d > rhs.d;
}
};
vector<int>E[maxn], W[maxn]; // E保存连接的物品 W保存优惠后的花费
int n, m, d[maxn];
bool vis[maxn];
int res;
int Dijkstra(int L, int R) {
for( int i=1; i<=n; i++ ) d[i] = INF;
d[1] = node[1].p;
priority_queue<PNode>q; // 优先队列优化
q.push(PNode(node[1].p, 1));
while(!q.empty()) {
PNode f = q.top(); q.pop();
//printf("ff = %d\n", f.u);
for( int i=0; i<E[f.u].size(); i++ ) {
int v = E[f.u][i];
if(node[v].l >= L && node[v].l <= R) {
if(d[v] > d[f.u] + node[v].p - (node[f.u].p-W[f.u][i])) {
d[v] = d[f.u] + node[v].p - (node[f.u].p-W[f.u][i]);
res = min(d[v], res); // res为最终结果
PNode tmp;
tmp.d = d[v];
tmp.u = v;
q.push(tmp);
}
}
}
}
return res;
}
int main() {
freopen("in", "r", stdin);
while(scanf("%d%d", &m, &n) != EOF) {
for( int i=1; i<=n; i++ ) E[i].clear(), W[i].clear();
for( int i=1; i<=n; i++ ) {
scanf("%d%d%d", &node[i].p, &node[i].l, &node[i].x);
for( int j=0; j<node[i].x; j++ ) {
int a, b;
scanf("%d%d", &a, &b);
E[i].push_back(a);
W[i].push_back(b);
}
}
res = node[1].p;
for( int i=node[1].l-m; i<=node[1].l; i++ ) { // 枚举交易中出现的地位的区间
Dijkstra(i, i+m);
}
printf("%d\n", res);
}
return 0;
}