글 읽기 - c++ 시간초과 질문드립니다.

celestial 3년 전 0

시간초과가 나는 것 같은데 일단 제가 짠 코드 자체도 맞는지 궁금하네요ㅜㅜ

도와주시면 감사합니다ㅜㅜ!!

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define MAX 1000000
#define N 801
#define E 200001
using namespace std;


typedef struct node {
	int vex;
	int cost;


	node(int a, int b) {
		vex = a;
		cost = b;
	}

	bool operator<(const node& b) const{
		return cost > b.cost;
	}
};

priority_queue<node> Q;


int dist[N][N];
bool check[N];
vector<pair<int, int>> map[E];

int v1, v2;
int n, e;
int mini = MAX;
int flag = 0;
void BFS(int ind) {
	ios::sync_with_stdio(false);
	int currentvex;
	int currentcost;

	while (!Q.empty()) {


		//여기가 전부 순회한 경우에 해당함
	/*	if (check[Q.top().vex] && check[n1] && check[n2]) {
			if (mini > Q.top().cost) {
				mini = Q.top().cost;
			}
		}*/

		currentvex = Q.top().vex;
		currentcost = Q.top().cost;
		Q.pop();
		//if (dist[ind][currentvex] < currentcost) { continue; }
		for (int i = 0; i < map[currentvex].size(); i++) {

			int nextvex = map[currentvex][i].first;
			int nextcost = map[currentvex][i].second+currentcost;

			if (dist[ind][nextvex] > nextcost) {

				dist[ind][nextvex] = nextcost;
				//check[nextvex] = true;
				Q.push(node(nextvex, nextcost));

			}

		}


	}





}





int main() {

	
	cin >> n >> e;


	for (int i = 1; i <= e; i++) {
		int snode, tnode, cost;
		cin >> snode >> tnode >> cost;
		map[snode].push_back(make_pair(tnode, cost));
		map[tnode].push_back(make_pair(snode, cost));
	}

	cin >> v1 >> v2;


	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) {
				dist[i][j] = 0;
			}
			else {
				dist[i][j] = MAX;
			}
		}
	}

	
	for (int i = 1; i <= n; i++) {
		dist[i][i] = 0;
		Q.push(node(i, 0));
		BFS(i);
	}
	
	/*for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			printf("%d ", dist[i][j]);
		}
		printf("\n");
	}*/



	int ans1 = min(dist[1][v1],dist[1][v2]);
	int ans2 = min(dist[v1][v2],dist[v2][v1]);
	int ans3 = min(dist[v1][n], dist[v2][n]);


	int ans = ans1 + ans2 + ans3;


	if (ans > MAX) {
		printf("-1");
	}
	else {
		printf("%d", ans);
	}




}

gkgg123 3년 전 1

제가 C++을 배워본적이 없어서 제대로 분석을 했는지 모르지만 일단 시간초과가 난 이유는 모든 경우에 대해서 다익스트라를 구했기 때문입니다.

이 문제는 총 3번의 다익스트라를 통해서 정답을 구할 수 있습니다.

힌트를 드리자면 양방향이기 때문에 A->B와 B->A의 경로의 값이 같습니다.

그렇기 때문에 A에 대한 다익스트라를 전부 구했다면, 굳이 B의 다익스트라를 다시 구하지 않더라도

A와 B 사이의 경로를 구할 수 있습니다.

이 점을 유의해서 풀어보시면 될것 같습니다.

그리고 제가 C++은 잘 몰라서 왜 그러는지 모르지만 ans를 int로 하면 틀렸습니다가 뜨고 long long을 해야 정답이 나오더군요.

이 두부분만 고치시면 될것 같습니다.

celestial 3년 전 0

@gkgg123 오오 님 정말 정말 감사합니다!! 한번 다시 고민해보고 도전해보겠습니다. 조언 정말 감사드려요*^^*

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

문제

문제

출처

ICPC

c++ 시간초과 질문드립니다.

celestial 3년 전 0

gkgg123 3년 전 1

celestial 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말