图论很重要
题目&＃xff1a;https://vjudge.net/contest/198762#problem/A
A - 昂贵的聘礼
为了方便起见&＃xff0c;我们把所有的物品从1开始进行编号&＃xff0c;酋长的允诺也看作一个物品&＃xff0c;并且编号总是1。每个物品都有对应的价格P&＃xff0c;主人的地位等级L&＃xff0c;以及一系列的替代品Ti和该替代品所对应的"优惠"Vi。如果两人地位等级差距超过了M&＃xff0c;就不能"间接交易"。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。
1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0
Sample Output
5250
题目意思&＃xff1a;
按例子讲&＃xff1a;
输入1和4 分别是1个等级差距限制和4个物品&＃xff08;相当与主人数&＃xff09;&＃xff0c;
输入 10000 3 2分别是 10000的价值的物品 3的主人等级 主人提出的两个物品兑换
输入 2 8000 分别是 2号物品&＃xff08;主人&＃xff09; &＃43; 8000金币数 才能兑换
输入 3 5000 同上
输入1000 2 1 分别是 1000的价值的物品 2的主人等级 主人提出的两个物品兑换
。。。。。。。
5250的得出 从第一个主人开始 &＃xff1a; 兑换3号物品&＃43;5000
然后 从3号主人开始 &＃xff1a; 兑换4号物品&＃43;200
再然后从4号主人开始 &＃xff1a;没有兑换的物品只能付50金币买物品
所付金币就为 5000&＃43;200&＃43;50&＃61;5250
题解&＃xff1a;
dijkstra&＃xff08;迪杰斯特拉&＃xff09;算法遍历图求最短路&＃43;等级制度的处理
dijkstra&＃xff08;迪杰斯特拉&＃xff09;算法&＃xff1a;https://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html&＃xff08;里面动态图挺容易懂的&＃xff09;
AC代码&＃xff1a;&＃xff08;网上抄的&＃xff09;
#include
#include
#include
using namespace std;
#define INF 0x3f3f3f3f
int mp[1100][1100];
int gg[11000];
int vis[11000];
int dis[11000];
int m,n;
int dijkstra()
{
int i,j;
memset(dis,0,sizeof(dis));
for(i&＃61;1; i<&＃61;n; i&＃43;&＃43;)//将从每一个点出发所需要的金币看做0到该点所需要的金币数目
dis[i]&＃61;mp[0][i];
for(i&＃61;1; i
int mina&＃61;INF;
int u,k;
for(j&＃61;1; j<&＃61;n; j&＃43;&＃43;)
{
if(!vis[j] && dis[j]
mina&＃61;dis[j];
u&＃61;j;
}
}
vis[u]&＃61;1;
for(k&＃61;1; k<&＃61;n; k&＃43;&＃43;)
{
if(!vis[k] && mp[u][k]
dis[k]&＃61;dis[u]&＃43;mp[u][k];
}
}
return dis[1];//返回每一个点到酋长处所花费的钱数
}
int main()
{
while(~scanf("%d%d",&m,&n))
{
int i,j,a,b,c,e,r;
for(i&＃61;0; i<&＃61;n; i&＃43;&＃43;)//初始胡为不能相通
for(j&＃61;0; j<&＃61;n; j&＃43;&＃43;)
mp[i][j]&＃61;INF;
for(i&＃61;1; i<&＃61;n; i&＃43;&＃43;)
{
scanf("%d%d%d",&a,&b,&c);
mp[0][i]&＃61;a;//将从每一个点出发所需要的金币看做0到该点所需要的金币数目
gg[i]&＃61;b;
for(j&＃61;1; j<&＃61;c; j&＃43;&＃43;)
{
scanf("%d%d",&e,&r);
mp[e][i]&＃61;r;//单向路径&＃xff0c;且等级e低于i&＃xff0c;低等级通向高等级
}
}
int minn&＃61;INF;
for(i&＃61;1; i<&＃61;n; i&＃43;&＃43;)//枚举每一个人为最低等级
{
int mnn&＃61;gg[i];
memset(vis,0,sizeof(vis));//注意初始化
for(j&＃61;1; j<&＃61;n; j&＃43;&＃43;)//标记等级差距过大&＃xff0c;和等级低于自己的人
{
if(gg[j]
vis[j]&＃61;1;
else
vis[j]&＃61;0;
}
int ss&＃61;dijkstra();
minn&＃61;min(minn,ss);
}
printf("%d\n",minn);
}
return 0;
}
转:https://www.cnblogs.com/huangzzz/p/7868429.html
京公网安备 11010802041100号