# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
103517 | pedro_sponchiado | 경찰관과 강도 (BOI14_coprobber) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "coprobber.h"
const int maxn=510;
vector<int> adj[maxn];
int d[maxn][maxn];
int marc[maxn];
queue<int> pilha;
vector<pair<int, pair<int, int> > > ord_d;
int aux[maxn][maxn];
int seta[maxn][maxn];
int p;
void bfs(int u, int ini){
marc[u]=1;
for(int i=0; i<adj[u].size(); i++){
int v=adj[u][i];
if(marc[v]==0){
d[v][ini]=d[u][ini]+1;
pilha.push(v);
}
}
pilha.pop();
return;
}
int start(int n, bool A[maxn][maxn]){
for(int i=1; i<=n; i++){
for(int k=1; k<=n; k++){
if(A[i][k]) adj[i].push_back(k);
}
}
//calcula as distancias
for(int i=1; i<=n; i++){
for(int k=1; k<=n; k++){
marc[k]=0;
}
pilha.push(i);
while(!pilha.empty())) bfs(pilha.front(), i);
}
//ordena pela distancia
for(int i=1; i<=n; i++){
for(int k=1; k<=n; k++){
ord_d.push_back(make_pair(d[i][k], make_pair(i, k)));
}
}
sort(ord_d.begin(), ord_d.end());
//calcula aux
for(int i=1; i<=n; i++){
for(int k=1; k<=n; k++){
aux[i][k]=maxn;
for(int t=0; t<adj[k].size(); t++){
int l=adj[k][t];
aux[i][k]=min(aux[i][k], d[i][l]);
}
}
}
//calcula pra cada nivel, quais são os caras que diminui distância, e
p=0;
return 0;
}
int nextMove(int r){
p=seta[p][r];
return p;
}