글 읽기 - 반례가 있을까요 고수님들 도와주세요..

(追記) (追記ここまで)

반례가 있을까요 고수님들 도와주세요..

13911번 - 집 구하기

isvara 4년 전 0

맥도날드 정점들과 연결되는 mac_dummy노드를 하나두고 weight은0으로 연결시키고

스타벅스도 마찬가지로 해서 그래프 만들고 dijstra두번 적용한코드입니다.

39퍼까지맞는데

혹시 반례가 있을까요?

#include<iostream>
#include<vector>
#include<math.h>
#include<string.h>
#include<set>
#include<queue>
#include<map>
#include<algorithm>
#define debug cout
typedef long long ll;
using namespace std;
const int max_n = 10001;
const int mac_dummy = 10002;
const int star_dummy = 10003;
const ll INF = 100000001;
int V, E;
int M, S;
ll x, y;
vector<pair<ll, ll>>adj[max_n+3];
vector<int>mac;
vector<int>star;
vector<ll>mac_dist, star_dist;
void input() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> V >> E;
	for (int i = 0; i < E; i++) {
		ll u, v, w;
		cin >> u >> v >> w;
		u--, v--;
		adj[u].push_back({ w,v });
		adj[v].push_back({ w,u });
	}
	cin >> M >> x;
	for (int i = 0; i < M; i++) {
		int v;
		cin >> v;
		v--;
		mac.push_back(v);
	}
	cin >> S >> y;
	for (int i = 0; i < S; i++) {
		int v;
		cin >> v;
		v--;
		star.push_back(v);
	}
}
void dijstra(int src,vector<ll>&dist) {
	priority_queue<pair<ll, ll>>pq;
	dist[src] = 0;
	pq.push({ 0,src });
	while (!pq.empty()) {
		ll node = pq.top().second;
		ll cost = -pq.top().first;
		pq.pop();
		if (dist[node] < cost)continue;
		for (int i = 0; i < adj[node].size(); i++) {
			ll nxt = adj[node][i].second;
			ll weight = adj[node][i].first;
			if (dist[nxt] > dist[node] + weight) {
				dist[nxt] = dist[node] + weight;
				pq.push({ -dist[nxt],nxt });
			}
		}
	}
}
void solve() {
	for (int i = 0; i < mac.size(); i++) {
		adj[mac_dummy].push_back({ 0,mac[i] });
		adj[mac[i]].push_back({ 0,mac_dummy });
	}
	for (int i = 0; i < star.size(); i++) {
		adj[star_dummy].push_back({ 0,star[i] });
		adj[star[i]].push_back({ 0,star_dummy });
	}
	mac_dist = vector<ll>(max_n + 3, INF);
	star_dist = vector<ll>(max_n + 3, INF);
	dijstra(mac_dummy,mac_dist);
	dijstra(star_dummy, star_dist);
	ll answer = 2*INF;
	for (int i = 0; i < V; i++) {
		if (mac_dist[i] <= x && star_dist[i] <= y && mac_dist[i]!=0 && star_dist[i]!=0)
			answer = min(answer, mac_dist[i] + star_dist[i]);
	}
	if (answer == 2 * INF) cout << -1;
	else cout << answer;
}
int main() {
	input();
	solve();
	return 0;
}

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

반례가 있을까요 고수님들 도와주세요..

isvara 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말