POJ 1062昂贵的聘礼（dijk最短路）

本文主要是介绍POJ 1062昂贵的聘礼（dijk最短路），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址：http://poj.org/problem?id=1062

妈蛋。。把mp数组初始化写到里边去了。。。每次输出一个都初始化了一遍。。这还有没有救。。。

这题看了一段时间，不会做。。主要是题目的数据范围给的非常不清楚。总想着只求一次最短路就可以。看了题解才发现枚举等级范围也不会超时。。然后后面 的就简单了

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <algorithm>using namespace std;
int n, m, mp[200][200], d[200], maxint=9999999, leave[200], dd[200], max2, vis[200];
void dijk(int s)
{int t, min1, pos, i, j;t=s+m;memset(vis,0,sizeof(vis));for(i=1;i<=n;i++){d[i]=dd[i];}for(i=1;i<n;i++){min1=maxint;for(j=1;j<=n;j++){if(leave[j]>=s&&leave[j]<=t&&!vis[j]&&min1>d[j]){min1=d[j];pos=j;}}vis[pos]=1;//printf("%d %d %d\n",pos,min1, d[1]);for(j=1;j<=n;j++){if(leave[j]>=s&&leave[j]<=t&&!vis[j]&&d[j]>d[pos]+mp[pos][j]){d[j]=d[pos]+mp[pos][j];}}}if(max2>d[1])max2=d[1];
}
int main()
{int  i, j, p, l, x, tt, v;scanf("%d%d",&m, &n);for(j=1;j<=n;j++){for(int k=1;k<=n;k++){mp[j][k]=maxint;}}for(i=0;i<n;i++){scanf("%d%d%d",&p,&l,&x);leave[i+1]=l;dd[i+1]=p;for(j=0;j<x;j++){scanf("%d%d",&tt,&v);mp[tt][i+1]=v;}}max2=1000000;for(i=leave[1]-m;i<=leave[1];i++){dijk(i);}printf("%d\n",max2);return 0;
}

这篇关于POJ 1062昂贵的聘礼（dijk最短路）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---