nyist 510昂贵的聘礼

/*

好好的图论题啊，最短路的应用，dijkstra算法

*/

#include <iostream>

using namespace std;

const int INF=100000;

int a[105][105],b[105],c[105],s[105],dist[105];

int n,m;

int dj(int p,int q)

{

	int i,j,r,t,k=0;

	for(i=0;i<n;i++)

	if((b[i]>=p&&b[i]<=q)) dist[i]=a[k][i], s[i]=0; else dist[i]=INF,s[i]=0;

	dist[0]=0; s[0]=1;

	for(i=1;i<n;i++)

	{

		t=INF;

		for(j=0;j<n;j++)

		if(!s[j]&&dist[j]<t) t=dist[j],k=j;

		s[k]=1;

		for(j=0;j<n;j++)

		if(!s[j]&&a[k][j]<INF&&b[j]>=p&&b[j]<=q)

		{

			r=dist[k]+a[k][j];

			if(dist[j]>r) dist[j]=r;

		}

	}

	t=c[0];

	for(i=0;i<n;i++)

    if(dist[i]+c[i]<t) t=dist[i]+c[i];

		return t;

}

int main(int argc, char *argv[])

{

	int i,j,k,p,q,l,r;

	while(cin>>m>>n&&(m||n))

	{

		for(i=0;i<n;i++)

		for(j=0;j<n;j++)

		a[i][j]=INF;

	for(i=0;i<n;i++)

	{

		cin>>c[i]>>b[i]>>k;

	    for(j=0;j<k;j++)

	    {

	    cin>>p>>q;

	    a[i][p-1]=q;

	    }

	}

	r=c[0];

     for(i=b[0]-m;i<=b[0];i++)

     {

	 k=dj(i,i+m);

	 if(k<r) r=k;

     }

     cout<<r<<endl;

	}

	return 0;

}
巴特西

nyist 510昂贵的聘礼

最新文章

热门文章
