글 읽기 - c++] 고수님들 도와주세요.... 풀수 있는 다른 로직이 있나요? (시간초과)

jeonyj1020 2년 전 0

각각의 편의점에서 다익스트라로 해결하려하였습니다.

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<deque>
#include<list>
#include<cstring>	
#include<sstream>
#include<set>
#include<map>
#include<cmath>
using namespace std;
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define INF 2000000000

int N, M, a, b, c;
vector<pair<int, int>> Map[5001];
vector<int>Home;
vector<int>Conv;

struct cmp {
	bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
		if (a.second != b.second) {
			return a.second > b.second;
		}
		else {
			return a.first > b.first;
		}
	}
};
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp>PQ;

int Dist[5001];

void Dijkstra(int start) {
	fill(Dist, Dist + N + 1, INF);

	Dist[start] = 0;
	PQ.push({ start,0 });

	while (!PQ.empty()) {
		auto now = PQ.top(); PQ.pop();

		int v = now.first, dist = now.second;

		if (Dist[v] < dist)continue;

		for (unsigned int i = 0; i < Map[v].size(); i++) {
			int nv = Map[v][i].first, ndist = Map[v][i].second;
			if (Dist[nv] > dist + ndist) {
				Dist[nv] = dist + ndist;
				PQ.push({ nv,dist + ndist });
			}
		}
	}
}
//init()
int p, q;
int dist_ans = INF;
int ANS;
int main() {
	fastio;
	cin >> N >> M;
	
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c;
		Map[a].push_back({ b,c }), Map[b].push_back({ a,c });
	}
	
	cin >> p >> q;
	for (int i = 0; i < p; i++) {
		int num; cin >> num;
		Home.push_back(num);
	}
	sort(Home.begin(), Home.end());

	for (int i = 0; i < q; i++) {
		int num; cin >> num;
		Conv.push_back(num);
	}
	for (int start = 0; start < q; start++) {
		Dijkstra(Conv[start]);
		for (int end = 0; end < p; end++) {
			if (dist_ans > Dist[Home[end]]) {
				dist_ans = Dist[Home[end]];
				ANS = Home[end];
			}
		}
	}
	cout << ANS;
	return 0;
}

sait2000 2년 전 4

처음 시작할 때 우선순위 큐에 모든 편의점을 한 번에 넣고 시작할 수 있습니다.

jeonyj1020 2년 전 0

아.. 그런 방법이 있군요 답변 정말 감사드립니다!!

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

문제

문제

출처

ICPC

c++] 고수님들 도와주세요.... 풀수 있는 다른 로직이 있나요? (시간초과)

jeonyj1020 2년 전 0

sait2000 2년 전 4

jeonyj1020 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말