글 읽기 - 질문있습니다. 살려주세요.

minjae200 5년 전 0

단순 다익스트라 알고리즘 써서 dist가 INF가 아니면 감염됫다는 뜻이므로 total을 플러스해주었고

가장 마지막에 감염된 컴퓨터라는 것은 첫 감염시작 컴퓨터로부터 감염시간이 가장 긴 컴퓨터가 마지막에 감염된것이라 생각하고 풀었습니다.

결과는 50프로에서 틀렸습니다가 나오는데 어디서 잘못되었는지 모르겠습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
#include <cstring>
#include <limits>
using namespace std;

#define MAX_C 10001
typedef long long ll;

const int INF = 987654321;
int n, d, c;
ll total, last;
bool visited[MAX_C];
vector<pair<ll, ll>> adj[MAX_C];
ll dist[MAX_C];
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;

void dijkstra(ll k, ll start)
{
	pq.push(make_pair(k, start));
	while (!pq.empty()) {
		ll curr;
		do {
			curr = pq.top().second;
			pq.pop();
		} while (!pq.empty() && visited[curr]);
		if (visited[curr]) {
			break;
		}
		visited[curr] = true;

		for (auto p : adj[curr]) {
			ll next = p.first;
			ll d = p.second;
			if (dist[next] > dist[curr] + d) {
				dist[next] = dist[curr] + d;
				pq.push(make_pair(dist[next], next));
			}

		}
	}
	for (int i = 1; i <= n; i++) {
		if (dist[i] != INF) {
			total++;
			if (dist[i] > last) last = dist[i];
		}
	}
}

int main(void)
{
	int tc; cin >> tc;
	while (tc--) {
		total = 0, last = 0;
		fill(dist, dist + MAX_C, INF);
		memset(visited, false, sizeof(visited));
		cin >> n >> d >> c;
		for (int i = 0; i < d; i++) {
			int a, b, s;
			scanf("%d %d %d", &a, &b, &s);
			adj[b].push_back(make_pair(a, s));
		}
		dist[c] = 0;
		dijkstra(0, c);
		cout << total << " " << last << endl;
	}
	return 0;
}

snrnsidy 5년 전 0

32줄에서 34줄 들어간 이유가 뭔가요??

그리고 visited배열 안쓰셔도 될거에요!

minjae200 5년 전 0

@joker_x 바꿔도안되네용 ㅠㅠㅠㅠㅠㅠ

snrnsidy 5년 전 1

adj 벡터를 전역변수로 사용하셨기에 clear를 매번 해줘야 합니다.

minjae200 5년 전 0

@joker_x

와.......감사합니다...사소한걸 체크못하고 로직을 보고잇엇네요 ㅠ .......

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

문제

문제

출처

ICPC

질문있습니다. 살려주세요.

minjae200 5년 전 0

snrnsidy 5년 전 0

minjae200 5년 전 0

snrnsidy 5년 전 1

minjae200 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말