晚上隨便找了一道練手題。開(kāi)始就看出是拓?fù)渑判颍瑢⒌燃?jí)限制先不考慮后，寫出個(gè)topo排序，再做更新處理。最后加上了等級(jí)限制。這題是一個(gè)考驗(yàn)理解能力的題目，本身算法不難。
well 編寫測(cè)試用例恰當(dāng)，一次AC。
less well 處理細(xì)節(jié)處有些魯莽，其實(shí)可以想明白的再改。注意memset是按位初始化。
/**//*
* Doc Name: 昂貴的聘禮
* Prob Id: 1062
* Serial Id: 2
* Author: LTE
* Date: 10/10/27
*/
#include <iostream>
using namespace std;
const int MAXN = 101;
int g[MAXN][MAXN];
int M,N;
bool visit[MAXN];
int topo[MAXN];
int tpi = 0;
struct V
{
int level;
int price;
};
V item[MAXN];
int a,b;
int i,j;
int en;
void dfsTopo(int v)
{
visit[v] = 1;
int i;
for(i=1; i<=N; i++)
{
if((g[v][i]!= -1)&&(!visit[i]))
dfsTopo(i);
}
topo[tpi++] = v;
}
int minGold()
{
for(i=0; i<tpi-1; i++)
{
for(j=i+1; j<tpi; j++)
{
if(g[topo[j]][topo[i]]>0)
{
int pr = g[topo[j]][topo[i]]+item[topo[i]].price;
if(pr < item[topo[j]].price)
item[topo[j]].price = pr;
}
}
}
return item[1].price;
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
memset(g, -1, sizeof(int)*MAXN*MAXN);
memset(visit, 0, sizeof(bool)*MAXN);
scanf("%d%d", &M, &N);
for(i=1;i<=N;i++)
{
scanf("%d%d%d", &item[i].price, &item[i].level, &en);
for(j=0; j<en; j++)
{
scanf("%d%d", &a, &b);
g[i][a] = b;
}
if( abs(item[i].level-item[1].level) > M )
{
for(j=1;j<N;j++) g[j][i]=-1;
}
}
dfsTopo(1);
printf("%d\n", minGold());
//system("PAUSE");
return 0;
}