Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!

求大佬帮助。。 查遍discuss所有数据。。dijkstra+等级枚举

Posted by hanyuweining at 2017-05-16 22:30:53 on Problem 1062
代码很丑,求轻喷【摊手】

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int INF=1000000;

int a[101],f[101][101],q[101];
int dist[101],use[101],r[101];
bool p[101];
int n,m;

int dijkstra(int low,int high)
{
	int i,b,j,l,x;
	memset(dist,0x3f,sizeof(dist));
	memset(use,0,sizeof(use));
	dist[1]=0;
	dist[0]=2147483647;
	for(i=1;i<=n;i++)
	{
		int w=0;
		for (int b=1;b<=n;b++)
		{
			if (!use[b] && (w==-1 || dist[b]<dist[w])&& q[b]>=low && q[b]<=high)
			{
				w=b;
			}
		}
		
		if (w==-1)
		{
			break;
		}
		use[w]=true;
		for (j=1;j<=n;j++)
		{
			if(f[w][j]!=2147483647&&q[j]>=low&&q[j]<=high)
			{	
				x=dist[j];
				dist[j]=min(dist[w]+f[w][j],dist[j]);
				if(x!=dist[j]&&a[r[j]]>a[w]&&q[j]>=low&&q[j]<=high)
				{
					r[j]=w;
				}
			}
		}
	}
	x=2147483647;
	for(i=1;i<=n;i++)
	{
		if(dist[i]+a[r[i]]<x&&q[i]>=low&&q[i]<=high)
		{
			x=dist[i]+a[r[i]];
		}
	}
	return x;
}

int main()
{
	int i,j,t,v,k;
	
	scanf("%d%d",&m,&n);
	for(i=0;i<101;i++)
	{
		for(j=0;j<101;j++)
		{
			f[i][j]=2147483647;
		}
	}
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d",&a[i],&q[i],&k);
		for(j=1;j<=k;j++)
		{
			scanf("%d%d",&t,&v);
			f[i][t]=min(f[i][t],v);
			f[t][i]=min(f[t][i],v);
		}
	}
	j=q[1];
	k=q[1]-m;
	t=2147483647;
	for(i=0;i<=m;i++)
	{
		for(v=1;v<=n;v++)
		{
			r[v]=v;
		}
		t=min(dijkstra(k+i,j+i),t);
	}
	
	printf("%d",t);
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator