AcWing903 昂贵的聘礼（最短路）
标签：gif 昂贵的聘礼 ace ice 不能 open click isp bool
本题我们可以把物品当作一个点，并且设立一个虚拟原点，然后加上一个限制是不能超过m个等级
因此枚举每个范围求一遍最短路就行，因为我们发现等级差距并不是很大，注意，酋长不一定是最大等级
#include
#include
#include
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int n, m;
int w[N][N], level[N];
int dist[N];
bool st[N];
int dijkstra(int down, int up)
{
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
dist[0] = 0;
for (int i = 1; i 1; i ++ )
{
int t = -1;
for (int j = 0; j )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
st[t] = true;
for (int j = 1; j )
if (level[j] >= down && level[j] up)
dist[j] = min(dist[j], dist[t] + w[t][j]);
}
return dist[1];
}
int main()
{
cin >> m >> n;
memset(w, 0x3f, sizeof w);
for (int i = 1; i 0;
for (int i = 1; i )
{
int price, cnt;
cin >> price >> level[i] >> cnt;
w[0][i] = min(price, w[0][i]);
while (cnt -- )
{
int id, cost;
cin >> id >> cost;
w[id][i] = min(w[id][i], cost);
}
}
int res = INF;
for (int i = level[1] - m; i 1]; i ++ ) res = min(res, dijkstra(i, i + m));
cout endl;
return 0;
}
View Code
AcWing903 昂贵的聘礼（最短路）
标签：gif 昂贵的聘礼 ace ice 不能 open click isp bool
原文地址：https://www.cnblogs.com/ctyakwf/p/12815301.html
评论