백준 BOJ 20160 - 야쿠르트 아줌마 야쿠르트 주세요

[원석방 산하 폐수방] 1일차 셋 div 2 B번.

뇌절오지게했다.

이놈의다익스트라 구현만 1e9번 했는데

아직도 못외웠다는점에서 코더가 멍청하다는걸 바로알수있다...

:blobsob:

 

https://www.acmicpc.net/problem/20160

20160번: 야쿠르트 아줌마 야쿠르트 주세요

보고 다익스트라는 빠르게 떠올랐었다.

 

야쿠르트 아줌마 경로구하는것도 그냥 다익스트라를 많이 돌려주면 해결된다.

쬐끔 까다로웠던 부분이 야쿠르트 아줌마가 i+1번째 지점으로 이동 불가능할때

i+2 i+3..... 이렇게 쭉 스킵하는 부분이었다.

 

그리고 이문제 확실하진 않지만 long long 넣어줘야 AC받을수있는듯? 하다.

 

#include <bits/stdc++.h>
#define INF 998244353
#define MINF 998244353998244353LL
typedef long long int ll;
using namespace std;

ll me[12345] = {0};
ll yogurt[12345] = {0};

vector<pair<int,int>> g[12345];
vector<int> ans;

int V,E;
int a,b,c;
int path[12] = {0};
int K;

void dijkstra(int node, int type){
	ll d[12345];
	for(int i=0; i<12345; i++) d[i] = MINF;
	
	d[node] = 0;
	priority_queue<pair<ll,int>> pq;
	pq.push({0, node});
	
	while(!pq.empty()){
		ll dis = -pq.top().first;
		int now = pq.top().second;
		pq.pop();
		
		if(d[now] < dis) continue;
		
		for(auto k : g[now]){
			int next = k.first;
			ll ndis = k.second + dis;
			
			if(d[next] > ndis){
				d[next] = ndis;
				pq.push({-ndis, next});
			}
		}
	}
	
	//type
	//1 -> me
	//2 -> yogurt
	for(int i=0; i<12345; i++){
		if(type==1){
			me[i] = d[i];
		}else{
			yogurt[i] = d[i];
		}
	}
}

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> V >> E;
	for(int i=0; i<E; i++){
		cin >> a >> b >> c;
		g[a].push_back({b,c});
		g[b].push_back({a,c});
	}
	for(int i=1; i<=10; i++) cin >> path[i];
	cin >> K;
	
	/*
	puts("------------------------------");
	for(int i=1; i<=V; i++){
		printf("%d : ", i);
		for(auto k : g[i]){
			printf("%d, ", k.first);
		}
		puts("");
	}
	puts("------------------------------");
	*/
	
	dijkstra(K,1);
	
	//printf("[ ");
	//for(int i=1; i<=V; i++){ printf("%d ", me[i]); }
	//puts("]");
	
	int now = path[1];
	ll time = 0;
	for(int i=1; i<=10; i++){
		dijkstra(now, 2);
		if(yogurt[path[i]] == MINF) continue;
		
		time += yogurt[path[i]];
		now = path[i];
		if(time >= me[path[i]]) ans.push_back(path[i]);
	}
	
	if(ans.size() == 0){
		cout << -1;
		return 0;
	}
	int ret = INF;
	for(auto k : ans) ret = min(ret, k);
	cout << ret;
	
	return 0;
}

맞왜틀 해결하겠다고 printf 왕창찍은게 더럽지만

귀찮으니 그대로 올릴거다

 

G3 부터 확실히 어려움....

열심히 재활해야 정올 나가겠다 ㅠㅠ

힘내야지