| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
手写队列+bfs竟然282ms,还2816K,复杂度是O(N2)啊果然弱渣所有程序都是又大又慢!
另外一开始数组开的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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator