昂贵的聘礼.doc

昂贵的聘礼.doc 昂贵的聘礼,pku1062, 这道目，我采用最短路径的Dijkstra算法，Dijkstra算法思想为:设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组， 第一组为已求出最短路径的顶点集合(用S示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将 加入到集合S中， 直到全部顶点都加入到S中，算法就结束了)，第二组为其余未确定最短路径的顶点集合(用U表示)， 按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中， 总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。 此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离， 是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。 但是直接用dijkstra肯定是不行的，如果对dijkstra做一些优化， 对每个目标节点做一次dijkstra的枚举就可以避免次优解的问题。 dijkstra算法的时候，指定一个目标节点，也就是说循环计 算该图的dijkstra，每次都是from 0 to i节点。 这样就能在一开始的时候得到0节点 和 目标节点能允许的 等级范围。 对dijkstra进行一些优化，比如当计算到目标节点已知的 时候就可以结束了。 要对题目理解透，级别差超过m的两个人是不能以任何方式 接触的，不单指相邻的两个人。 以下是代码: #include #define MAX_NODE 100 #define MAX_D 100000000 int M, N; struct _Node { int p; int l; }Node[MAX_NODE]; int Engle[MAX_NODE][MAX_NODE] = {0}; struct _Table { int k; int d; int max_l; int min_l; }Table[MAX_NODE]; int result = MAX_D; void dijkstra(int t) { int i, min_d, min_n; int max_l, min_l; for (i = 0; i < N; ++i) { Table[i].k = 0; Table[i].d = MAX_D; Table[i].max_l = Node[i].l + M; Table[i].min_l = Node[i].l - M; } Table[0].d = 0; max_l = Table[0].max_l < Table[t].max_l ? Table[0].max_l : Table[t].max_l; min_l = Table[0].min_l > Table[t].min_l ? Table[0].min_l : Table[t].min_l; while (!Table[t].k) { min_d = MAX_D; min_n = -1; for (i = 0; i < N; i++) { if (!Table[i].k && Table[i].d < min_d) { min_d = Table[i].d; min_n = i; } } if (-1 == min_n) break; { if ( min_l <= Node[i].l && Node[i].l <= max_l && !Table[i].k && Engle[min_n][i] && Table[i].d > Engle[min_n][i] + Table[min_n].d) { Table[i].d = Engle[min_n][i] + Table[min_n].d; } } Table[min_n].k = 1; } if (Table[t].k && result > Table[t].d + Node[t].p) { result = Table[t].d + Node[t].p; } } void main() { int P, L, X; int T, V; int i, n = 0; scanf("%d %d", &M, &N); while (EOF != scanf("%d %d %d", &P, &L, &X)) { Node[n].l = L; Node[n].p = P; for (i = 0; i < X; ++i) { scanf("%d %d", &T, &V); Engle[n][T - 1] = V; } n++; } for (i = 0; i < N; ++i) { dijkstra(i); } printf("%d\n", result); }