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

手写队列+bfs竟然282ms,还2816K,复杂度是O(N2)啊

Posted by KatrineYang at 2016-07-25 16:26:40 on Problem 1161 and last updated at 2016-07-25 16:28:05
果然弱渣所有程序都是又大又慢!
另外一开始数组开的252,WA,改成302就AC了,这是坑人嘛,题目不是说最多250个嘛。
#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;

struct node{
	int val;
	node *prev, *next;
	node(int v): val(v), prev(NULL), next(NULL){}
};

int main() {
	int M, N, L;
	scanf("%d%d%d", &M, &N, &L);
	int clubs[32];
	for(int i = 0; i < L; i++){
		scanf("%d", &clubs[i]);
	}
	int reg_[302][302] = {0};
	int dian[302][302] = {0};
	int dianNum[302] = {0};
	for(int i = 1; i <= M; i++){
		int len;
		scanf("%d", &len);
		int start, q, h;
		scanf("%d", &start);
		dian[start][dianNum[start]] = i;
		dianNum[start] ++;
		q = start;
		for(int j = 0; j < len-1; j++){
			scanf("%d", &h);
			dian[h][dianNum[h]] = i;
			dianNum[h] ++;
			reg_[q][h] = i;
			q = h;
		}
		reg_[q][start] = i;
	}
	int connNum[302] = {0};
	int connList[302][302];

	for(int i = 1; i <= N-1; i++){
		for(int j = i+1; j <= N; j++){
			int a = reg_[i][j], b = reg_[j][i];
			if(a > 0 && b > 0){
				connList[a][connNum[a]] = b;
				connNum[a] ++;
				connList[b][connNum[b]] = a;
				connNum[b] ++;
			}
		}
	}
	int dist[302][302];
	for(int i = 1; i <= N; i++){
		node *st = new node(i);
		dist[i][i] = 0;
		bool state[302] = {false};
		state[i] = true;
		node *head = st, *tail = st;
		while(head != NULL){
			int cur = head->val;
			if(head == tail){
				head = NULL;
				tail = NULL;
			}
			else{
				head->next->prev = NULL;
				head = head->next;
			}
			for(int j = 0; j < connNum[cur]; j++){
				int idx = connList[cur][j];
				if(state[idx]) continue;
				state[idx] = true;
				dist[i][idx] = dist[i][cur] + 1;
				if(head == NULL){
					node *temp = new node(idx);
					head = temp;
					tail = temp;
				}
				else{
					node *temp = new node(idx);
					tail->next = temp;
					temp->prev = tail;
					tail = tail->next;
				}
			}
		}
	}
	int res = 2147483647;
	for(int i = 1; i <= M; i++){
		//如果选在i
		int tempRes = 0;
		for(int j = 0; j < L; j++){
			int Dian = clubs[j];
			int Min = 2147483647;
			for(int k = 0; k < dianNum[Dian]; k++){
				int temp = dist[i][dian[Dian][k]];
				if(temp < Min) Min = temp;
			}
			tempRes += Min;
			if(tempRes >= res) break;
		}
		if(tempRes < res) res = tempRes;
	}
	printf("%d\n", res);
	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