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

Re:wa到不行啊,floyd超时,djkis就是wa,求代码~感激不禁。

Posted by skogt at 2010-08-11 14:36:37 on Problem 2394
In Reply To:Re:wa到不行啊,floyd超时,djkis就是wa,求代码~感激不禁。 Posted by:skogt at 2010-08-11 14:35:45
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN=510;
#define inf 0xfffffff
int map[MAXN][MAXN];
int f,p,c,m;
bool visited[MAXN];
int dis[MAXN];


int main()
{
	int u,v,w;
	int x;
	while(scanf("%d%d%d%d",&f,&p,&c,&m)!=EOF)
	{
		for(int i=1;i<=f;i++)
			for(int j=1;j<=f;j++)
				map[i][j]=inf;
		while(p--){
			scanf("%d%d%d",&u,&v,&w);
			if(w<map[u][v])
				map[u][v]=map[v][u]=w;
		}
		int a[110];
		for(int i=1;i<=f;i++){
			dis[i]=map[1][i];
			visited[i]=false;
		}
		dis[1]=0;
		for(int i=1;i<=f;i++){
			int min=inf;
			for(int j=1;j<=f;j++)
				if(!visited[j] && min>dis[j])
					min=dis[x=j];
			visited[x]=true;
			for(int j=1;j<=f;j++)
				if(!visited[j] && dis[j]>dis[x]+map[x][j])
					dis[j]=dis[x]+map[x][j];
		}
		int j=0;
		int k;
		for(int i=1;i<=c;i++){
			scanf("%d",&k);
			if(dis[k]<=m)
				a[j++]=i;
		}
		sort(a,a+j);
		printf("%d\n",j);
		for(int i=0;i<j;i++)
			printf("%d\n",a[i]);
	
	}

	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