4641931_ac_47ms_300k.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 88 行

#include<iostream>
using namespace std;
int m,n;
int rank[105];
bool open[105];
bool now[105];
int opn;
int path[105][105];
int dis[105];
int tmin;
int pickmin()
{
	int xmin=1000000,ymin;
	for(int i=0;i<=n;i++)
	{
		if(open[i]==true&&dis[i]<xmin)
		{
			ymin=i;
			xmin=dis[i];
		}
	}
	return ymin;
}
int Dijkstra(int low,int high)
{
	//memset(close,false,sizeof(close));
	memset(open,false,sizeof(open));
	memset(now,false,sizeof(open));
	memset(dis,1000000,sizeof(dis));
	int i;
	open[0]=true;
	now[0]=true;
	opn=1;//cln=0;
	for(i=1;i<=n;i++)
	{
		if(rank[i]>=low&&rank[i]<=high) {open[i]=true;now[i]=true;opn++;}
	}
	dis[0]=0;
	//for(i=0;i<=n;i++) cout<<dis[i]<<" "<<open[i]<<" ";cout<<endl;
	//cout<<opn<<endl;
	while(opn!=0)
	{
		int temp;
		temp=pickmin();
		//cout<<temp<<endl;
		open[temp]=false;opn--;
		for(i=0;i<=n;i++)
		{
			if(path[temp][i]!=0&&now[i]==true)
			{
				if(dis[i]>dis[temp]+path[temp][i])
				{
					dis[i]=dis[temp]+path[temp][i];
				}
			}
		}
		//for(i=0;i<=n;i++) cout<<dis[i]<<" ";cout<<endl;
	}
	return dis[1];
}
int main()
{
	while(cin>>m)
	{
		cin>>n;
		int i,j,temp,t2,t3;
		memset(path,0,sizeof(path));
		for(i=1;i<=n;i++)
		{
			cin>>path[0][i]>>rank[i]>>temp;
			for(j=1;j<=temp;j++)
			{
				cin>>t2>>t3;
				path[t2][i]=t3;
			}
		}
		tmin=10000;
		//for(i=0;i<=n;i++) cout<<rank[i]<<" ";
		for(i=rank[1];i<=rank[1]+m;i++)
		{
			int temp=Dijkstra(i-m,i);
			//cout<<temp;
			if(temp<tmin) tmin=temp;
		}
		cout<<tmin<<endl;
	}
	return 0;
}