글 읽기 - 채점 기준 혹은 서버에 대한 질문입니다.

yjyj1027 4년 전 0

이 문제에 대해 정확히 같은 소스코드를 2번 제출했는데,

한번은 TLE, 한번은 AC를 받았습니다.

두 제출일 사이에 채점 기준 변동에 대한 알림도 받지 못했습니다.

이런 일이 처음이라 어떤 경우에 이런 일이 생길 수 있는지 질문드립니다.

혹시 몰라 소스코드를 첨부합니다.

#include <iostream>
#include <cstdio>
#include <math.h>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#define INF 10000000000000
#define MAX 100010
using namespace std;

bool vis[MAX];
long long dist[MAX];

long long V, E, k, s, u, v, w;

vector<long long> adj[MAX];
map<pair<long long, long long>, long long> length;

priority_queue < pair<long long, long long>, vector < pair<long long, long long>>, greater<pair<long long, long long>>> pq;

void Dijkstra() {
	while (!pq.empty()) {
		pair<long long, long long> tmp = pq.top();
		pq.pop();
		if (vis[tmp.second]) continue;
		vis[tmp.second] = true;

		for (long long newv : adj[tmp.second]) {
			if (length[{tmp.second, newv}] == 0) continue;
			if (dist[newv] > tmp.first + length[{tmp.second, newv}]) {
				dist[newv] = tmp.first + length[{tmp.second, newv}];
				pq.push({ dist[newv], newv });
			}
		}
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> V >> E >> k;
	fill(dist, dist + V + 1, INF);

	for (long long i = 0; i < E; i++) {
		cin >> u >> v >> w;
		if (length[{v, u}] == 0) {
			length[{v, u}] = w;
			//length[{v, u}] = w;
			adj[v].push_back(u);
			//adj[v].push_back(u);
		}
		else {
			if (w >= length[{v, u}]) continue;
			length[{v, u}] = w;
			//length[{v, u}] = w;
		}
	}
	for (long long i = 0; i < k; i++) {
		cin >> s;
		dist[s] = 0;
		pq.push({ 0, s });
	}

	Dijkstra();
	long long mx = 0, mxidx;
	for (long long i = V; i >= 1; i--) {
		if (dist[i] >= mx) {
			mxidx = i;
			mx = dist[i];
		}
	}
	cout << mxidx << "\n" << mx;
	return 0;
}

djm03178 4년 전 1

원래 실행할 때마다 걸리는 시간은 조금씩 다를 수밖에 없기 때문에 1초 제한인 문제에 800ms대라면 그 차이에 의해 제출할 때 운이 안 좋으면 1초를 넘어갈 수 있어 보입니다.

또는 확인해보지는 않았지만 어딘가에 undefined behavior가 숨어있을지도 모릅니다.

yjyj1027 4년 전 0

해결되었습니다. 감사합니다!

hun3102 4년 전 1

입력, 출력 횟수가 많을 경우는 cin, cout이 아닌 scanf, printf를 사용하시면 해결될 것 같습니다.
시간 속도 차이는 구글에서 참고 하시면 됩니다.
저도 바꿔서 844ms -> 448ms로 줄었습니다.

yjyj1027 4년 전 0

이런 방법도 있군요! 감사합니다!

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

문제

문제

출처

ICPC

채점 기준 혹은 서버에 대한 질문입니다.

yjyj1027 4년 전 0

djm03178 4년 전 1

yjyj1027 4년 전 0

hun3102 4년 전 1

yjyj1027 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말