poj1062 昂贵的聘礼 (dijkstra最短路算法)

POJ 1062 昂贵的聘礼

题意:  大致意思就是寻找一条路,使得到达编号为1的点的总代价最少且这条路上的任意两点间的等级差不超过m,  每个点有各自的权值, 每条边(i, j)的权值指的是可替换j的权值;

解法:   取任一点假设为最优路中等级最低的点, 将<该等级的点以及与该等级等级差超过m的点去掉; 然后进行dijkstra最短路算法, 取剩下点中权值最小的点进行遍历

code:

/*************** Problem from :1062 Problem describe : data: ****************/ #include<iostream> #include<cstdlib> #include<cstdio> #include<algorithm> #include<cmath> #include<map> #include<stack> #include<queue> #include<ctime> #include<cstring> #include<vector> #include<string> #define ll __int64 using namespace std; const int inf = 0x3f3f3f3f; const int maxn=105; int min_p; int p[maxn], edge[maxn][maxn], vis[maxn] ,L[maxn], d[maxn], x[maxn]; void init(){ memset(edge, -1, sizeof(edge)); memset(L, 0, sizeof(L)); memset(p, -1, sizeof(p)); min_p=inf; return ; } int min(int a, int b){ return (a<b)?a:b; } int n, m ; void dijkstra() { int i, j, k; for(i=1; i<=n; i++) d[i] = p[i]; //将所有的点的d赋值为该点的权值 while(true){ int v=-1, MIN=inf; for(i=1; i<=n; i++){ if(!vis[i] && d[i]<MIN){ MIN = d[v = i]; } } if(v==-1) break; vis[v]=1; for(i=1; i<=n; i++){ if(!vis[i] && edge[v][i]!=-1){ d[i] = min(d[v]+edge[v][i], d[i]); } } } min_p = min(min_p, d[1]); return ; } int main() { int i, j, k, id, pi; //freopen("in.txt","r",stdin); while(~scanf("%d%d", &m, &n)) { init(); for(i=1; i<=n; i++){ scanf("%d %d %d", &p[i], &L[i], &x[i]); for(j=1; j<=x[i]; j++){ scanf("%d %d", &id, &pi); edge[id][i] = (edge[id][i]<0)?pi:min(edge[id][i], pi); } } for(i=1; i<=n; i++){ if(L[i]<L[1]-m || L[i]>L[1]+m) continue; //与L[1]不满足条件的点必定不会出现在最优路中 for(j=1; j<=n; j++){ if( L[j]<L[i]-m || L[j]>L[i] ) vis[j] = 1; //设L[i]为等级最小的那个点 去掉不符合条件的点 else vis[j]=0; } dijkstra(); } printf("%d\n", min_p); } return 0; }