글 읽기 - 4%... 반례가 뭐가 있을까요?

airplane9876 5년 전 0

여러가지 경우 해봤는데 반례 찾는게 너무 힘드네요..

#include <stdio.h>
#include <algorithm>
using namespace std;
const int INF = 1000000000;
int dist[501][501][2];//[][][0] : 방해 0번받음 [][][1] : 방해 1번받음
int disturb[501];
int main() {
	int n, m, q;//도시, 도로, 질문
	scanf("%d %d %d", &n, &m, &q);
	for(int i= 1; i<= n; i++) {
		scanf("%d", &disturb[i]);
	}
	
	for(int i = 1; i <= n; i++) {
		for(int j= 1; j <= n; j++) {
			dist[i][j][0] = i==j? 0 : INF;
			dist[i][j][1] = i==j? disturb[i] : INF;
		}
	}
	for(int i= 0; i < m; i++) {
		int s, e, c;
		scanf("%d %d %d", &s, &e, &c);

		
		dist[s][e][0] = min(dist[s][e][0], c);
		dist[e][s][0] = min(dist[e][s][0], c);
		dist[s][e][1] = max(dist[s][e][0] + disturb[s], dist[s][e][0] + disturb[e]);
		dist[e][s][1] = max(dist[e][s][0] + disturb[s], dist[e][s][0] + disturb[e]);

	}

	for(int k= 1; k <= n; k++) {
		for(int i= 1; i <= n; i++) {
			for(int j= 1; j<= n; j++) {
				dist[i][j][0] = min(dist[i][j][0], dist[i][k][0] + dist[k][j][0]);
				

			}
		}
	}


	for(int k= 1; k <= n; k++) {
		for(int i= 1; i <= n; i++) {
			for(int j= 1; j <= n; j++) {
				dist[i][j][1] = min(dist[i][j][1], max(dist[i][k][0] + dist[k][j][1], dist[i][k][1] + dist[k][j][0]));
			}
		}
	}

	while(q--) {
		int s, e;
		scanf("%d %d", &s, &e);
		if(s < 1 || s > n || e < 1 || e > n) printf("-1\n");
		else if(dist[s][e][1] == INF) printf("-1\n");
		else printf("%d\n", dist[s][e][1]);
	}


	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

4%... 반례가 뭐가 있을까요?

airplane9876 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말