该题是做最短路专题时的题，但是可惜没有想到如何进行最短路求解。倒是觉得dfs能够得到结果，因为该题对于建立边有严格的条件，递归能够很好的解决这个约束。
每次递归时将当前路径的最低等级和最高等级传递下去，然后再进行判断。这里还要注意判定环的存在。后者没有注意的话会MLE。
代码如下：
#include#include #include #include #include #define MAXN 105using namespace std;int M, N, hash[MAXN];struct dot{ int num, p; struct dot *next;};struct Node{ int p, rank, cnt; struct dot *next;}e[105];int build(int x, int low, int high){ int fee, Min = e[x].p; for (struct dot *ptr = e[x].next; ptr; ptr = ptr->next) { if ((abs(high - e[ptr->num].rank) <= N) && (abs(low - e[ptr->num].rank) <= N)) { if (!hash[ptr->num]) { hash[ptr->num] = 1; fee = ptr->p + build(ptr->num, min(low, e[ptr->num].rank), max(high, e[ptr->num].rank)); hash[ptr->num] = 0; Min = min(Min, fee); } } } return Min;} int main(){ struct dot *temp; scanf("%d %d", &N, &M); for (int i = 1; i <= M; ++i) { scanf("%d %d %d", &e[i].p, &e[i].rank, &e[i].cnt); e[i].next = NULL; for (int j = 1; j <= e[i].cnt; ++j) { temp = (struct dot *)malloc(sizeof (struct dot)); scanf("%d %d", &temp->num, &temp->p); temp->next = e[i].next; e[i].next = temp; } } hash[1] = 1; printf("%d\n", build(1, e[1].rank, e[1].rank)); return 0;}
网上的一份纯c代码，够精简啊！
int g[100][100],a[100][100],pri[100],lvl[100]; void main(){ int m,n,i,j,k,t,p,ans,u; scanf("%d %d",&m,&n); for(i=0;i =lvl[0]-m+u) a[i][j]=g[i][j]; else a[i][j]=100000; } } for(k=0;k a[0][i]+pri[i]) ans=a[0][i]+pri[i]; } printf("%d\n",ans); }