http://acm.nyist.net/JudgeOnline/problem.php?pid=510

本文主要是介绍http://acm.nyist.net/JudgeOnline/problem.php?pid=510，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意中文不解释。。

思路：以每个物品当做图中的顶点，以优惠的价格为边权，建图，这里让求需要的最少金币，故可以转化为最短路问题，这里引入一个超级源点0，可以看做是每个物品都可以和自己交换，但没有优惠价格，当找不到可交换的物品时（只能和自己交换），则返回当前的最短路径长度，即是所需要的最少金币。

#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<queue>
#include<cstdio>
#define  N 105
using namespace std;
struct Gnode
{Gnode() {}Gnode(int len,int num):len(len),num(num) {}int len,num;
};
struct Gnode1
{Gnode1() {}Gnode1(int num,int dis,int maxlev,int minlev):num(num),dis(dis),maxlev(maxlev),minlev(minlev) {}int num,dis,maxlev,minlev;bool operator< (const Gnode1 &now) const{return now.dis<dis;}
};
int lev[N],dlev;
int dijkstra(vector<vector<Gnode> >&Graph)
{priority_queue<Gnode1> Q;Q.push(Gnode1(1,0,lev[1],lev[1]));while(1){Gnode1 cur=Q.top();if(cur.num==0) return cur.dis;for(int i=0;i<Graph[cur.num].size();++i){if(Graph[cur.num][i].num==0||(cur.maxlev-lev[Graph[cur.num][i].num]<=dlev&&lev[Graph[cur.num][i].num]-cur.minlev<=dlev)){int maxx=max(cur.maxlev,lev[Graph[cur.num][i].num]);int minx=min(cur.minlev,lev[Graph[cur.num][i].num]);Q.push(Gnode1(Graph[cur.num][i].num,cur.dis+Graph[cur.num][i].len,maxx,minx));}}Q.pop();}
}
int main()
{int n;while(cin>>dlev>>n&&dlev&&n){vector<vector<Gnode> >Graph (n+1);memset(lev,0,sizeof(lev));for(int i=1;i<=n;++i){int price,m;cin>>price>>lev[i]>>m;Graph[i].push_back(Gnode(price,0));for(int j=0;j!=m;++j){int a,b;cin>>a>>b;Graph[i].push_back(Gnode(b,a));}}cout<<dijkstra(Graph)<<endl;}return 0;
}

这篇关于http://acm.nyist.net/JudgeOnline/problem.php?pid=510的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---