입력으로 주어지는 사건들의 관계를 방향그래프로 생각하면 사건 A와 사건 C 사이에 A->B->C 의 순서가 되는 사건 B가 있으면, 사건 C는 사건 A 이후에 발생했다는 사실을 알 수 있다.
플로이드 와샬을 통해 각 사건들의 관계를 모두 구하면 s줄에 걸친 물음에 대답할 수 있다.
#include <cstdio>
bool v[401][401];
int main(){
int n, m;
scanf("%d %d", &n, &m);
while(m--){
int s, e;
scanf("%d %d", &s, &e);
v[s][e] = true;
}
for(int k=1; k<=n; ++k){
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j){
v[i][j] |= v[i][k] & v[k][j];
}
}
}
scanf("%d", &m);
while(m--){
int s, e;
scanf("%d %d", &s, &e);
if(v[s][e]) puts("-1");
else if(v[e][s]) puts("1");
else puts("0");
}
return 0;
}
댓글 2개:
안녕하세요
저도 이 문제 시도 했었는데요.
저또한 Floyd알고리즘을 사용했는데 시간 초과로 실패합니다. 계속 채점중에 4%에서 멈춰 있다가 시간 초과로 죽는데, 전혀 모르겠습니다. 혹시 한번 봐 주실수 있나요?
#include
#include
using namespace std;
int n, k;
int map[401][401], ck[401];
void init() {
int go = 0, to = 0;
scanf("%d", &n);
scanf("%d", &k);
for (int i = 0; i < k; i++) {
scanf("%d%d", &go, &to);
map[go][to] = 1;
}
}
void makeMap() {
for (int x = 1; x <= n; x++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
map[i][j] = (map[i][x] & map[x][j]);
}
}
}
}
void result() {
int m = 0;
int x = 0, y = 0;
scanf("%d", &m);
for (int i = 0; i < m; i++) {
scanf("%d%d", &x, &y);
if (map[x][y] == 1) {
cout << "-1" << endl;
}
else if (map[y][x] == 1) {
cout << "1" << endl;
}
else{
cout << "0" << endl;
}
}
}
int main() {
init();
makeMap();
result();
return 0;
}
댓글 감사합니다.
우선, map[i][j] = (map[i][x] & map[x][j]); 가 아니라 map[i][j] |= (map[i][x] & map[x][j]); 입니다.
대입 연산이 아닌 OR 중첩연산을 하셔야합니다. (이미 연결된 길은 연결된 상태로 유지해야하기 때문이죠)
그리고 만약 위 소스가 시간초과를 받으신다면 cout<<"1"<<endl 이 아니라 puts("1") 이나 printf("1\n") 을 사용하시는걸 추천합니다.
cout과 endl은 출력 버퍼를 비우는 등 어쩌고저쩌고한 이유로 상당히 느립니다. (scanf, printf의 2배~8배 정도. 참고링크: https://algospot.com/forum/read/2496/)
댓글 쓰기