#include<stdio.h>
#include<iostream>
using namespace std;
#define NULL 0 
int r,n,m;
int map[112][12002];
struct node
{
	int t,l,d;
	node *next;
};
node *head[102];
#define inf 10002000
int best;
int min(int a,int b)
{
	return a>b?b:a;
}
int dp(int city,int cost)
{
	if(city<0||city>n||cost<0||cost>m)return inf;
	if(map[city][cost]!=-1)return map[city][cost];
	if(city==n)return 0;
	int ans=inf;
	node *tmp=head[city];
	while(tmp!=NULL)
	{
		ans=min(ans,dp(tmp->d,cost+tmp->t)+tmp->l);
		tmp=tmp->next;
	}
	map[city][cost]=ans;
//	printf("%d %d %d \n",city,cost,ans);
	return ans;
}
int main()
{
	scanf("%d%d%d",&m,&n,&r);
	int i,s,d,l,t;
	for(i=1;i<=n;i++)
	{
		head[i]=(node*) malloc(sizeof(node*));
		head[i]=NULL;
	}
	node *tmp;
	for(i=0;i<r;i++)
	{
		scanf("%d%d%d%d",&s,&d,&l,&t);
		tmp=(node*) malloc(sizeof(node*));
		tmp->d=d;tmp->l=l;tmp->t=t;
		tmp->next=head[s];
		head[s]=tmp;
	}
	memset(map,-1,sizeof(map));
	best=inf;
	int ans=dp(1,0);
//	if(best==inf)
//	else
	if(ans>=inf)printf("-1\n");
	else printf("%d\n",ans);
	return 0;
}

• Re:为何我一直Runtime Error？我的做法是直接Dp求到达某点花费为x的最短长度？为何是Runtime error呢？ (7) goodpeter 2007-09-13 02:02:02