題目鏈接：昂貴的聘礼
這個題對自己收獲挺大的，模板要自己經常敲，才能理解，要自己經常敲，從能溫故而知新，自己以前總結的建圖方式，做題的時候要會用，要敢用，否則==NULL。
題意對於交換條件描述的有點不清楚，這裡解釋一下，假設8件物品，等級差距不能超過3，酋長LV 5，所以可以進行交換的LV區間是[2,5][3,6][4,7][5,8]，不必考慮題目那一句，“但是如果他和某個地位較低的人進行了交易，地位較高的的人不會再和他交易，他們認為這樣等於是間接接觸，反過來也一樣”。越看越暈，只要符合以上區間的都可以進行交換。
思路：開始看題時，自己的思路有點偏差，認為P神只能從價格最便宜、等級最低的那個人開始首次交易，後來敲了。。。再後來。。無從下手了，看了一下Discuss，噢，枚舉啊，Discuss上的神牛門大多用Dijkstra 或 Bellman-Ford過的，還剪枝...俺還學啊。然後，我想Bellman-Ford能過的SPFA肯定也能過，但是SPFA怎麼敲，忘了。。又重新復習最短路 And 建圖方式，開敲1遍A。中間的小細節自己處理的不好，還不會調程序，又叫P神過來了。。。。
ME TIME
720kb 32ms
#include
#include
#include
#include
#include
const int Size = 99999;
const int INF = 1<<20;
const int N = 101;
const int MMM = 10010;
using namespace std;
int NN,M,l = 0;
struct node{
int v,w,next;
}edge[MMM];
int p[N],lv[N],num,t;
int dis[N],vis[N],lim,low;
int q[MMM],head[MMM];
int SPFA(int S,int E)
{
//printf("low = %d high = %d\n",low,lim);
int s = 0,e = 0;
for(int i = 1;i<=N;i++)
dis[i] = p[1];
dis[S] = 0;
q[e++] = S;
vis[S] = 1;
while(s < e)
{
int tmp = q[s++];
for(int i = head[tmp];i!=0;i=edge[i].next)
{
if((lv[edge[i].v]>=low && lv[edge[i].v]<=lim )&& (dis[edge[i].v]> dis[tmp] + edge[i].w))
{
dis[edge[i].v] = dis[tmp] + edge[i].w;
if(!vis[edge[i].v])
{
q[e++] = edge[i].v;
vis[edge[i].v] = 1;
}
}
}
vis[tmp] = 0;
}
return dis[E];
}
void add(int a,int b,int c) //前向星建圖
{
edge[t].v = b;
edge[t].w = c;
edge[t].next = head[a];
head[a] = t;
t++;
}
/*void Print()
{
int k,i;
for(i = 0; i <= NN; i++)
{
if(head[i])
{
for(k = head[i]; k != 0; k = edge[k].next)
{
printf("%d->%d %d\n", i, edge[k].v, edge[k].w);
}
}
}
}*/
int main()
{
int a,b;
while(~scanf("%d%d",&M,&NN))
{
l = 0;
t = 1;
memset(head,0,sizeof(head));
for(int i = 1;i<=NN;i++)
{
scanf("%d%d%d",&p[i],&lv[i],&num);
add(0,i,p[i]);
for(int j = 0;j
