AcWing 903. DJ
原题链接
中等
作者:
cyzh
,
2022-03-01 00:48:22
,
所有人可见
,
阅读 653
时间复杂度O(N^3)
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int main(){
int n, k; cin >> k >> n;
vector<vector<int>> g(n + 1, vector<int>(n + 1, 1e9));//存边(稠密图)
vector<int> w(n + 1), lev(n + 1);//价值,地位
for(int i = 1; i <= n; i++){
int x; cin >> w[i] >> lev[i] >> x;
while(x--){
int a, b; cin >> a >> b;
g[a][i] = b;//用a 换得 i 需要 b金币
}
}
int ans = 2e9;
for(int i = 1; i <= n; i++){//遍历地位区间
priority_queue<pii, vector<pii>, greater<pii>> q;//
vector<int> d(n + 1, 1e9);//存金币数
bitset<110> v;//是否来过
for(int j = 1; j <= n; j++)
if(lev[j] >= i && lev[j] <= i + k){//满足地位在区间[i, i + k]中
d[j] = w[j], q.push({w[j], j});
}
while(q.size()){
int x = q.top().second; q.pop();
if(v[x]) continue; v[x] = 1;//
for(int j = 1; j <= n; j++)
if(lev[j] >= i && lev[j] <= i + k && d[j] > d[x] + g[x][j]){//j 在地位区间中 && j 可以用x以更加低的价格拿到
d[j] = d[x] + g[x][j];
q.push({d[j], j});
}
}
ans = min(ans, d[1]);//取答案
}
cout << ans;
return 0;
}
tql