程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> nyist 510昂貴的聘禮

nyist 510昂貴的聘禮

編輯:C++入門知識

/*
好好的圖論題啊,最短路的應用,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;
}        

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved