글 읽기 - 시간초과 관련해서 질문 드립니다

dk10211 3년 전 0

가장 큰 가중치를 지닌 가선을 계속 전파하는 방식으롤 진행을 하였는데 시간초과가 나네요.

이런식으로 풀어서는 시간초과를 절대 못피하나요? 아니면 일부 수정을 하고 추가를 하면 시간초과 없이 풀 수 있나요?

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int d[10005];
int INF = 2000000000;
vector<pair<int,int>>v[10005];
priority_queue<int>pq;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back(make_pair(b, c));
		v[b].push_back(make_pair(a, c));
	}
	int s, e;
	cin >> s >> e;
	pq.push(s);
	d[s] = INF;
	while (!pq.empty()) {
		int now = pq.top();
		pq.pop();
		for (unsigned int i = 0; i < v[now].size(); i++) {
			int next = v[now][i].first;
			int data = v[now][i].second;
			int k = min(d[now], data);
			if (d[next] < k) {
				d[next] = k;
				pq.push(next);
			}
		}
	}
	cout << d[e];
}

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

문제

문제

출처

ICPC

시간초과 관련해서 질문 드립니다

dk10211 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말