UC知道poj1062 昂贵的聘礼
来源：百度知道 编辑：UC知道 时间：2024/06/04 11:56:52
谁能告诉我这个错在哪里了 几组数据我都试过了 还是WA
用的遍历可能的等级区间，把不在这区间里的点的代价置为最大，再对图用Dijkstra，最后取最小的。
#include<iostream>
using namespace std;
#define MAX 999999
class node
{
public:
node():L(MAX),father(0),DW(0),P(0),in(false){}
int L;
int father;
int DW;
int P;
bool in;
};
int main()
{
int limit,num;
scanf("%d%d",&limit,&num);
node *V=new node[num];
int A[num][num];
for(int i=0;i<num;++i)
for(int j=0;j<num;++j)
A[i][j]=MAX;
for(int i=0;i<num;++i)
{
int X;
scanf("%d%d%d",&V[i].P,&V[i].DW,&X);
if(X!=0)
{
int v,weight;
for(int j=0;j<X;++j)
{
scanf("%d%d",&v,&weight);
A[i][v-1]=A[v-1][i]=weight;
}
用的遍历可能的等级区间，把不在这区间里的点的代价置为最大，再对图用Dijkstra，最后取最小的。
#include<iostream>
using namespace std;
#define MAX 999999
class node
{
public:
node():L(MAX),father(0),DW(0),P(0),in(false){}
int L;
int father;
int DW;
int P;
bool in;
};
int main()
{
int limit,num;
scanf("%d%d",&limit,&num);
node *V=new node[num];
int A[num][num];
for(int i=0;i<num;++i)
for(int j=0;j<num;++j)
A[i][j]=MAX;
for(int i=0;i<num;++i)
{
int X;
scanf("%d%d%d",&V[i].P,&V[i].DW,&X);
if(X!=0)
{
int v,weight;
for(int j=0;j<X;++j)
{
scanf("%d%d",&v,&weight);
A[i][v-1]=A[v-1][i]=weight;
}
你的代码好乱啊,改了好久vc++6.0才能编译通过....是devcpp的产品吧
那个,你注意这道题里使用的是有向图,而你是当成无向图做的...导致有些路径会被反搜比如以下:
1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
10000 2 0
你的结果是6400,路径是1-3-4-2,而4-2的路径本来是没有的,只有2-4...
实际结果应该是8000
附上我ac的纯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<n;i++)for(j=0;j<n;j++)g[i][j]=100000;
for(i=0;i<n;i++){
scanf("%d %d %d",&pri[i],&lvl[i],&k);
for(j=0;j<k;j++){
scanf("%d %d",&t,&p);
g[i][t-1]=p;
}
}
for(i=0;i<n;i++)g[i][i]=0;
ans=pri[0];
for(u=0;u<=m;u++){
for(i=0;i<n;i++)for(j=0;j<n;j++){
if(lvl[j]<=lvl[0]+u&&lvl[j]>=lvl[0]-m+u)a[i][j]=g[i][j];
else a[i][j]=100000;
}
for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)
if(a[i][k]+a[k][