글 읽기 - 시간초과 도와주세요 ㅠㅠ [다익스트라, c++]

loveto3 4년 전 0

다익스트라로 풀이해보았고 50퍼센트에서 시간초과가 납니다.

정답은 맞는거같은데..;

후보 목적지에 대해서 다익스트라 2번씩(후보목적지,출발노드) 쓴게 화근일까요? 출발노드에 대해선 한번만 써도 되긴할텐데..

조언좀 부탁드립니다~!

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <algorithm>
#define MAX 50000001
using namespace std;
vector<vector<pair<int,int> > > mp; // 매핑 2차원 벡터 
int* dp= new int[2001]; // 노드의 값 
int* check= new int[2001]; // 노드 방문 여부 
void dijkstra(int);

//다익스트라로 풀이 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int testCase;
	cin>>testCase;
	for(int tc=0;tc<testCase;tc++){
	mp.clear(); // 케이스마다 맵 클리어 

	int WGH;
	int n,m,t;
	cin>>n>>m>>t;
	int start,g,h;
	cin>>start>>g>>h;
	//2차원 벡터 생성 
	for(int i=0;i<n+1;i++){
		vector<pair<int,int> > red;
		mp.push_back(red);
	}
	//맵 입력  (이 부분에서 g,h의 가중치 구하려고 if식 썻는데 더 좋은 방법이 있을까요 @@; ) 
	int a,b,d;
	for(int i=0;i<m;i++){
		cin>>a>>b>>d;
		if((a==g && b==h) || (a==h && b==g) ){
			WGH= d;
		}
		mp[a].push_back(make_pair(b,d));
		mp[b].push_back(make_pair(a,d));
	}
	// 목적지 후보 벡터로 입력 
	vector<int> destinations;
	for(int i=0;i<t;i++){
		int tmp;
		cin>> tmp;
		destinations.push_back(tmp);
	}
	vector<int> ans;
	//목적지 후보에 대해서 다익스트라 ( 이부분에서의 중복 연산 때문인지..) 
	for(int k:destinations){
		bool flag=true;
		dijkstra(k);  // 목적지 후보에서 다익스트라 
		int toG = dp[g];
		int toH = dp[h];
		dijkstra(start); // 출발지에서 다익스트라 
		int toHome = dp[k];
		int gtoHome = dp[g];
		int htoHome = dp[h];

		if(min(toG,toH)+WGH != max(toG,toH)) flag=false;
		if(toG>toH){
			if(gtoHome+toG!=toHome) flag=false;
		}else{
			if(toH+htoHome!=toHome) flag = false;
		}
		if(flag){
			ans.push_back(k);
		}
	}
	sort(ans.begin(),ans.end());
	for(int k:ans){
		cout<<k<<" ";
	}
	cout<<'\n';
	
	}
}

void dijkstra(int a){
	//최소우선순위큐 생성 
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
	pq.push(make_pair(0,a));
	//dp와 check 초기화 
	fill(dp,dp+2001,MAX);
	fill(check,check+2001,0);
	dp[a]=0;
	//다익스트라 
	while(!pq.empty()){
		int dpValue = pq.top().first;
		int nodeNum = pq.top().second;
		pq.pop();
		if(check[nodeNum]==0){
			for(auto k: mp[nodeNum]){
				int nextNodeNum = k.first;
				int weight = k.second;
				if(dpValue+weight < dp[nextNodeNum]){
					dp[nextNodeNum]=dpValue+weight;
				}
				pq.push(make_pair(dp[nextNodeNum],nextNodeNum));
			}
		}
		check[nodeNum]=1;
	}
}

loveto3 4년 전 0

출발지에서의 다익스트라를 한번만 햇더니 시간문제가 해결되었습니다~

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <algorithm>
#define MAX 50000001
using namespace std;
vector<vector<pair<int, int> > > mp;
int* dp = new int[2001];
int* dpForStart = new int[2001];
int* check = new int[2001];
void dijkstra(int);
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int testCase;
	cin >> testCase;
	for (int tc = 0; tc < testCase; tc++) {
		mp.clear();
		//	fill(dp,dp+2001,MAX);
		//	fill(check,check+2001,0);
		int WGH;
		int n, m, t;
		cin >> n >> m >> t;
		int start, g, h;
		cin >> start >> g >> h;
		for (int i = 0; i < n + 1; i++) {
			vector<pair<int, int> > red;
			mp.push_back(red);
		}
		int a, b, d;
		for (int i = 0; i < m; i++) {
			cin >> a >> b >> d;
			if ((a == g && b == h) || (a == h && b == g)) {
				WGH = d;
			}
			mp[a].push_back(make_pair(b, d));
			mp[b].push_back(make_pair(a, d));
		}
		vector<int> destinations;
		for (int i = 0; i < t; i++) {
			int tmp;
			cin >> tmp;
			destinations.push_back(tmp);
		}
		vector<int> ans;
		dijkstra(start);
		for (int i = 0; i < 2001; i++) {
			dpForStart[i] = dp[i];
			//cout << dpForStart[i] << " ";
		}
		//cout << '\n';
		for (int k : destinations) {
			bool flag = true;
			dijkstra(k);
			int toG = dp[g];
			int toH = dp[h];
			int toHome = dp[start];

			int gtoHome = dpForStart[g];
			int htoHome = dpForStart[h];
			//		cout<<toG<<toH<<toHome<<gtoHome<<htoHome<<'\n';
			if (min(toG, toH) + WGH != max(toG, toH)) flag = false;
			if (toG > toH) {
				if (gtoHome + toG != toHome) flag = false;
			}
			else {
				if (toH + htoHome != toHome) flag = false;
			}
			if (flag) {
				ans.push_back(k);
			}
		}
		sort(ans.begin(), ans.end());
		for (int k : ans) {
			cout << k << " ";
		}
		cout << '\n';

	}
}

void dijkstra(int a) {
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
	pq.push(make_pair(0, a));
	fill(dp, dp + 2001, MAX);
	fill(check, check + 2001, 0);
	dp[a] = 0;
	while (!pq.empty()) {
		int dpValue = pq.top().first;
		int nodeNum = pq.top().second;
		pq.pop();
		if (check[nodeNum] == 0) {
			for (auto k : mp[nodeNum]) {
				int nextNodeNum = k.first;
				int weight = k.second;
				if (dpValue + weight < dp[nextNodeNum]) {
					dp[nextNodeNum] = dpValue + weight;
				}
				pq.push(make_pair(dp[nextNodeNum], nextNodeNum));
			}
		}
		check[nodeNum] = 1;
	}
}

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

문제

문제

출처

ICPC

시간초과 도와주세요 ㅠㅠ [다익스트라, c++]

loveto3 4년 전 0

loveto3 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말