【POJ 1062】 昂贵的聘礼
附加一个小判断的最短路
这个题配得上这标题。。。有一个弯确实不好拐 反正我开始没想出来 然后居然水过去了！！ 没错 POJ这数据。。。 很久前做的 最近根据计划训练又翻出来 看了看discussion 发现两组数据WA 重新想了想 改成了正规做法
其实就是由一号物品(首领物品/目标物品)的地位 向上 向下延伸出了一段可交易地位的范围 [level[1]-m, level[1]+m] 而要令一条路中所有点都符合条件 只需要每两点间距离不超过地位限制 即不断枚举区间的两端 使每次枚举出的区间长度恰为地位限制[level[1], level[1]+m] 至 [level[1]-m, level[1]] 枚举过程中出现的最短的一条 即为最短路径 想通后一怒之下写了三种解法。。。给自己蠢哭~~(>_<)~~
Dijkstra写法
;int dv[111];int mp[111][111];int p[111];int dis[111];bool vis[111];int n,m;int Dijkstra(int u,int h,int l){int mn = INF,i,j;memset(vis,0,sizeof(vis));memset(dis,-1,sizeof(dis));dis[u] = 0;int w,k;for(i = 0; i <= n; ++i){w = INF;k = -1;for(j = 1; j <= n; ++j){if(!vis[j] && dis[j] < w && dis[j] != -1){w = dis[j];k = j;}}if(k == -1) return mn;mn = min(mn,dis[k] + p[k]);vis[k] = 1;for(j = 1; j <= n; ++j){if(!vis[j] && (dis[j] == -1 || dis[j] > dis[k] + mp[k][j]) && dv[j] >= l && dv[j] <= h){dis[j] = dis[k] + mp[k][j];}}}}int main(){int i,x,v,h,l;scanf(“%d %d”,&m,&n);memset(mp,INF,sizeof(mp));int Min = INF;for(i = 1; i <= n; ++i){scanf(“%d %d %d”,&p[i],&dv[i],&x);while(x–){scanf(“%d”,&v);scanf(“%d”,&mp[i][v]);}}for(h = dv[1]+m,l = dv[1]; h >= dv[1]; –h,–l){Min = min(Min,Dijkstra(1,h,l));}printf(“%d\n”,Min);return 0;}
BellMan-Ford写法
;typedef struct Edge{int u,v,ct,next;}Edge;Edge eg[111111];int head[111];int dv[111];int mp[111][111];int p[111];int dis[111];int n,m,tp;void Add(int u,int v,int ct){eg[tp].u = u;eg[tp].v = v;eg[tp].ct = ct;head[u] = tp++;}int BellMan(int u,int h,int l){int i,v,ct,j;memset(dis,INF,sizeof(dis));dis[u] = 0;int mn = p[u];for(i = 0; i < n; ++i){for(j = 0; j < tp; ++j){u = eg[j].u;v = eg[j].v;ct = eg[j].ct;if(dis[v] > dis[u] + ct && dv[v] >= l && dv[v] <= h){dis[v] = dis[u] +ct;mn = min(mn,dis[v] + p[v]);}}}return mn;}int main(){tp = 0;int i,x,v,h,l,ct;scanf(“%d %d”,&m,&n);memset(mp,INF,sizeof(mp));int Min = INF;for(i = 1; i <= n; ++i){scanf(“%d %d %d”,&p[i],&dv[i],&x);while(x–){scanf(“%d %d”,&v,&ct);Add(i,v,ct);}}for(h = dv[1]+m,l = dv[1]; h >= dv[1]; –h,–l){Min = min(Min,BellMan(1,h,l));}printf(“%d\n”,Min);return 0;}
SPFA写法
;typedef struct Edge{int v,ct,next;}Edge;Edge eg[111111];int head[111];int dv[111];int mp[111][111];int p[111];int dis[111];bool vis[111];int n,m,tp;void Add(int u,int v,int ct){eg[tp].v = v;eg[tp].ct = ct;eg[tp].next = head[u];head[u] = tp++;}int SPFA(int u,int h,int l){int i,v,ct,mn;memset(vis,0,sizeof(vis));memset(dis,INF,sizeof(dis));queue <int> q;q.push(u);dis[u] = 0;mn = p[u];while(!q.empty()){u = q.front();q.pop();vis[u] = 0;for(i = head[u]; i != -1; i = eg[i].next){v = eg[i].v;ct = eg[i].ct;if(dis[v] > dis[u] + ct && dv[v] >= l && dv[v] <= h){dis[v] = dis[u] + ct;mn = min(mn,dis[v] + p[v]);if(!vis[v]){q.push(v);vis[v] = 1;}}}}return mn;}int main(){tp = 0;int i,x,v,h,l,ct;scanf(“%d %d”,&m,&n);memset(mp,INF,sizeof(mp));memset(head,-1,sizeof(head));int Min = INF;for(i = 1; i <= n; ++i){scanf(“%d %d %d”,&p[i],&dv[i],&x);while(x–){scanf(“%d %d”,&v,&ct);Add(i,v,ct);}}for(h = dv[1]+m,l = dv[1]; h >= dv[1]; –h,–l){Min = min(Min,SPFA(1,h,l));}printf(“%d\n”,Min);return 0;}
，只有他的好身体，没有地方可去，只想到处流浪、人生就像一场旅行，
