프밍노트

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

위 이미지처럼 

X = 얼음

.   = 호수

L  =  백조

하루마다 호수에 맞닿아 있는 얼음이 녹는다.

백조는 며칠뒤에 서로 만날 수 있을지 구하는 문제이다.

여기 주소에서 데이터를 받아볼수있다.

https://hsin.hr/2005/ 

문제 풀이에 사용한 알고리즘은 

BFS , UnionFind  두개다

문제는 아래 두가지 라고 생각했다.

1.얼음을 녹일 방법

2.백조가 만날수 있는지 확인할수 있는 방법

해결방식 

1.얼음의 외각을 녹일때 다음 녹을 얼음을 지정해 큐에 넣어준다.

2.얼음마다 지역을 설정해둔뒤 다른지역과 합쳐질때 서로 합쳐준다.

코드

#include<iostream>
#include <queue>
using namespace std;
vector<pair< int, int>> Swans;
queue<pair<int, int>> X_queue, TempQueue, * PointerQueue, * TempPointerQueue;
const static vector < vector<int>> Mover{ {1,0},{0,1},{-1,0},{0,-1} };
const static vector < vector<int>> InputMover{ {0,-1},{-1,0} };
vector<int> lakeList;

int UnionFInd(int Num) {
	if (lakeList[Num] == Num)
		return Num;
	return lakeList[Num] = UnionFInd(lakeList[Num]);
}

void Union(int Left, int Right) {
	int LNum = UnionFInd(Left);
	int RNum = UnionFInd(Right);
	if (LNum == RNum)return;
	if (LNum > RNum) {
		lakeList[LNum] = RNum;
	}
	else {
		lakeList[RNum] = LNum;
	}
}
enum Tile
{
	X = -88,
	x = -120,
	L = -76,
	dot = -46
};
void SwanLake() {
	int R, C;
	cin >> R >> C;
	vector<vector<int>> lake(R, vector<int>(C));
	vector< int> L_Point(2);
	int numb = 1;
	lakeList.push_back(0);
	for (int i = 0; i < R; ++i) {
		for (int j = 0; j < C; ++j) {
			char chardata;
			cin >> chardata;
			lake[i][j] = -(int)chardata;
			if (chardata == 'L') Swans.push_back({ i,j });
			int after = -1, before = -1;

			for (auto M : InputMover) {
				if (0 > i + M[0] || 0 > j + M[1] || R <= i + M[0] || C <= j + M[1])continue;
				if ((lake[i][j] == Tile::dot || lake[i][j] == Tile::L) && lake[i + M[0]][j + M[1]] == Tile::X) {
					X_queue.push({ i + M[0],j + M[1] });
					lake[i + M[0]][j + M[1]] = Tile::x;
				}
				if (lake[i][j] == Tile::X && lake[i + M[0]][j + M[1]] > 0) {
					X_queue.push({ i,j });
					lake[i][j] = Tile::x;
				}

				if ((lake[i][j] == Tile::dot || lake[i][j] == Tile::L) && lake[i + M[0]][j + M[1]] > 0) {
					if (after == -1) {
						after = lake[i + M[0]][j + M[1]];
					}
					else {
						before = lake[i + M[0]][j + M[1]];
					}

				}
			}
			if ((lake[i][j] == Tile::dot || lake[i][j] == Tile::L)) {
				if (after == -1) {
					lake[i][j] = numb;
					lakeList.push_back(numb++);

				}
				else if (before == -1) {
					lake[i][j] = after;
				}
				else {
					Union(after, before);
					lake[i][j] = UnionFInd(after);
				}
			}


		}
	}

	for (int i = 0; i < 2; ++i) {
		L_Point[i] = (lake[Swans[i].first][Swans[i].second]);
	}
	int day = 0;
	if (UnionFInd(L_Point[0]) == UnionFInd(L_Point[1])) {
		cout << day;
		return;
	}


	do {
		day++;
		PointerQueue = &((X_queue.empty()) ? TempQueue : X_queue);
		TempPointerQueue = &((!X_queue.empty()) ? TempQueue : X_queue);
		while (!PointerQueue->empty())
		{
			auto data = PointerQueue->front();
			PointerQueue->pop();
			int Isbridge = 0;
			int firstbridge = -1, secondbridge = -1;

			for (auto M : Mover) {
				if (0 > data.first + M[0] || 0 > data.second + M[1] || R <= data.first + M[0] || C <= data.second + M[1])continue;
				if (lake[data.first + M[0]][data.second + M[1]] == Tile::X)
				{
					lake[data.first + M[0]][data.second + M[1]] = Tile::x;
					TempPointerQueue->push({ data.first + M[0] ,data.second + M[1] });
				}
				else if (lake[data.first + M[0]][data.second + M[1]] >= 0) {

					if (Isbridge != 0) {
						Union(lake[data.first][data.second], lake[data.first + M[0]][data.second + M[1]]);
					}
					else {
						Isbridge = lake[data.first + M[0]][data.second + M[1]];
						lake[data.first][data.second] = Isbridge;
					}
				}
			}
		}

		if (UnionFInd(L_Point[0]) == UnionFInd(L_Point[1]))break;


	} while (!TempPointerQueue->empty());
	cout << day;
}



int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	SwanLake();

}

해당문제는 그래프  최소 스패닝 트리로 풀 수 있는 문제다.

최소 스패닝트리는 프림과 크루스칼 알고리즘 으로 플수있다.

해당문제는  프림으로 풀었다 프림이 기본적인 알고리즘은 더 쉽다.

간단하게 말하자면  다익스트라가 누적과 다음노드로 가는 가격을 본다면

프림의 경우는 현재 갈 수 있는 간선들 중 가장 값싼 간선을 우선적으로 본다는 것이다,.

다시 문제로 돌아와

"켜져 있는"위치로만 가야 하기에 다익스트라는 다시 왔을 때 가격을 비교해야 하기에 어울리지 않을 수 있다.

코드르 보면서 설명해 보자

#include<iostream>
#include <queue>
#include<tuple>
#include<vector>
#include <unordered_map>
using namespace std;
unordered_map<int, vector<pair<int, int>>> Spninmap;
unordered_map<int, bool> maps;
//unordered_map<int, int> sp_map;
int gagungchi = 0;
int k = 0;
priorityqueue<pair<int, int>> q;
void minSpningTree() {
    int a = 0, b = 0;
    int n = 0, m = 0, v = 0;
    while (true)
    {
        Spninmap = *new unordered_map<int, vector<pair<int, int>>>();
        maps = *new unordered_map<int, bool>();
        gagungchi = 0;
        k = 0;
        cin >> a >> b;
        if (a == 0 && b == 0) return;
        //그래프로 섬들을 만들어준다.
        for (int i = 0; i < b; i++) {
            cin >> n >> m >> v;
            Spninmap[n].push_back(make_pair(-v, m));
            Spninmap[m].push_back(makepair(-v, n));
            k += v;
        }
        //시작위치 n 으로 잡고 갈수있는 간선들을 받아준다.
        for (auto i : Spninmap[n]) {
            q.push(i);
        }
        //현재위치 탐색완료
        maps[n] = true;
        while (!q.empty())
        {
            auto c = q.top();
            q.pop();
            if (maps[c.second] == true) continue;
            maps[c.second] = true;
            //전력 업데이트
            gagungchi += -(c.first);
            //현재 갈수있는 간선들 추가
            for (auto i : Spninmap[c.second]) {
            //갔던섬이면 빼주기
                if (maps[i.second] == true) continue;
                q.push(i);
            }
        }
        cout << k - gagungchi<<"\n";
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin.tie(NULL);
    minSpningTree();
    return 0;
}

종이 자르기 문제

위처럼 종이가 주어지면 흰색 부분과 파란 부분을 분리하여 자르되

정사각형이 되도록  자르는게 목적이다.

해당 문제는 한칸씩 확인하며 정사각형을 측정한다면

틀렸을때 최적이 될 정사각형을 찾아야 하기에

중복 되는 탐색이 매우 많을 것 같은 느낌이다.

이문제는 모든 사각형을 정사각형으로 자른다가 핵심이라고 생각한다.

가장 큰 종이에서 나올 수 있는 최대 정 사각형은 4개 그 안에서도 4개로 오히려 쪼개면서 계산하는 것이다.

사실 문제에서 내용을 이미지로 간단하게 설명해준다.

위 이미지 순서대로 큰거 자르고 문제 있는 부분만 자르면서 들어가는식으로 풀면된다

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> arrya;
int color[2] = {0,0};

//재귀함수
void Recursive(int size, int x, int y) {
	int  a = arrya[x][y];
	bool is_same = false;
	
    //해당 크기의 정사각형 완전탐색하며 문제있는지 확인
    for (int i = x; i < x + size; i++) {
		for (int j = y; j < y + size; j++) {
			if (arrya[i][j] != a)
			{
				is_same =true;
				break;
			}
		}
		if (is_same)break;
	}
    //정사각형 4개로 나눠서 재귀
	if (is_same) {
		size /= 2;
		Recursive(size, x, y);
		Recursive(size, x + size, y);
		Recursive(size, x, y + size);
		Recursive(size, x + size, y + size);
	}
	else {
    //다채워졌다면 사각형이니 +1
		color[a]++;
	}





}



void solution() {
	int size;
	cin >> size;
	arrya = vector<vector<int>>(size);

	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			int z = 0;
			cin >> z;
			arrya[i].push_back(z);
		}
	}
	Recursive((size ), 0, 0);
	cout << color[0] << "\n"<<color[1];




}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);


	solution();
	return 0;
}

토마토마토마토

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

익지 않은 토마토는 근처 토마토를 익게 하는 문제 

혼자 익는경우가 없을때

모든 토마토가 익을때까지 최소일수 를 구하는 문제

간단하게 BFS 를 써서 푸는 문제다 

골드 5인만큼 그냥 시뮬레이션 돌리면 풀린다.

#include<iostream>
#include<vector>
#include<queue>
#include <tuple>
using namespace std;

#define XYZ tuple<int,int>

vector<XYZ> nonfire;
const XYZ MoverDirection[4] = { {1,0} ,{-1,0} ,{0,-1} ,{0,1} };
vector<vector<int>> vec;
int N = 0, H = 0;

///토마토 익는칸 확인 함수
vector<XYZ> findNextTomato(vector<XYZ> _xyz) {

	vector<XYZ> firebe = {};
	for (auto a : _xyz) {
		for (auto Dir : MoverDirection) {
			int  xyz2[2] = { get<0>(a) + get<0>(Dir),get<1>(a) + get<1>(Dir) };

			if (!(get<0>(a) + get<0>(Dir) < N && get<0>(a) + get<0>(Dir) >= 0 &&
				get<1>(a) + get<1>(Dir) < H && get<1>(a) + get<1>(Dir) >= 0)) {
				continue;
			}

			if (vec[xyz2[0]][xyz2[1]] == 0) {
				firebe.push_back(XYZ(xyz2[0], xyz2[1]));
				vec[xyz2[0]][xyz2[1]] = 1;
			}
		}
	}
    //익은것들 위치반환
	return firebe;
}


int main() {


	cin >> H >> N ;

	vector<XYZ> fire;
	int answer = 0;
	for (int i = 0; i < N; i++) {
		vec.push_back({});
		for (int j = 0; j < H; j++)
		{
			int a;
			cin >> a;
			vec[i].push_back(a);

			if (a == 1)
			{
				fire.push_back(XYZ(i, j));
			}
			if (a == 0) {
				nonfire.push_back(XYZ(i, j));
			}

		}
	}

	while (true)
	{
    
		if (fire.size() <= 0)
			break;
		//다음으로 익을 토마토 구하기
        fire = findNextTomato(fire);
		
        //일자 업데이트 
		answer++;
	}
    
	for (auto a : nonfire) {
		if (vec[get<0>(a)][get<1>(a)] == 0)answer = 0;
	}
	cout << (answer - 1);

}

익은 위치와 익지않은 위치를 받아준뒤

}

while{

       func (익은 토마토들) 

             return이제 익은 토마토 위치 반환

        반복하며 answer+1

}

}

위와 같은 행위를  결국 익을게 없을때 까지 반복한다.

더이상 익을게 없을때

안익었던 토마토들이 아직도 익지않았는지 확인한다.

매우 쉬운코드 

예전에 짠코드여서 왜 그랬는지 모르겠지만 queue를 써봤다가 안쓰고 vector로 풀어보려고 풀어보았던거 같다.

queue로 BFS를 풀고 얕은복사를 좀더 활용하는게 좋을거같다.

만약 시각적으로 보면서 확인해야 이해하기 쉬울거 같다 생각한다면! 

	while (true)
	{
		if (fire.size() <= 0)
			break;
		fire = findNextTomato(fire);

		//cout << endl;

		for (auto x : vec) {
			for (auto y : x) {
				cout << y;
				cout << " ";
			}
			cout << endl;

		}

		answer++;
	}

를 추가해서 점점 퍼지는걸 볼수있따 :-)

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

통학이 너무나도 하기 싫었던 영우는 결국 학교의 기숙사에 들어갔다. 통학의 고통에서 해방된 기쁨도 잠시, 학교 기숙사에서는 일정 기간마다 청소 검사를 한다는 사실을 알게 되었다. 청소 검사에서 나쁜 점수를 받으면 벌점을 받게 되고, 벌점이 많이 쌓이면 기숙사에서 퇴사 해야 한다. 영우는 어떤 경우에 벌점을 받는지 궁금하여 기숙사에서 진행하는 청소 검사 시스템에 대해 자세히 조사해 보았다. 기숙사 청소 검사 시스템은 오늘로부터 정확히 t 일이 지나고 검사를 하며, 검사 시간 단축을 위해 방의 특정 부분만 검사한다. 하지만 검사하는 특정 부분 중 한 곳이라도 더럽다면 영우는 벌점을 받게 된다. 영우가 사는 방은 N * N 정사각형 방이며, 기숙사 방바닥에는 곰팡이가 서식하고 있다. 곰팡이는 1 일이 지날 때마다 특이한 방식으로 증식하는데, 그림 1(a)의 곰팡이는 1 일이 지나면 그림 1(b)와 같이 8 군데로 증식되고, 원래의 곰팡이는 사라진다. 만약 곰팡이가 증식해야 하는 부분이 벽으로 막혀 있다면, 그곳으로는 증식하지 못한다. 그림 2 는 두 군데의 곰팡이가 1 일이 지난 후 모습이다.

위 그림은 증식방식이다.

해당문제는 처음 보았을때 단순 시물레이션 문제와 같다고 생각할수 있지만

그냥 구현하게 된다면  반복적인 처리로인해 계산해야 하는 곰팡이가 기하급수적으로 늘어난다

해당 문제를 잘 생각해본다면 최적화 할수있는 부분이 쉽게 보인다.

중앙에서 시작할경우 퍼지는 모습은 아래와 같다

위 이미지로 알수있는것은  이동 했던 칸에서 다시 원래자리에 곰팡이를 복구 시킨다는 사실이다.

그렇다면 해당 위치에 곰팡이가 생기고 하나라도 이동했을경우엔 무한정 곰팡이가 번식한다는 이야기다...으...

그렇다면 두번째로 생각할수있는것은 

해당 위치에서 1턴 쉬면서 반복한다 라는것은 

홀수날과 짝수날을 구분지어 두개의 영우의방을 돌아가면 계산한다면,

해당 위치가 이미 곰팡이가 있었던 적이 있었는지도 간단하게 체크할수있다.

BFS를 사용해서 반복체크를 할때 다음 날의 위치가 일전에 도달한적 있는 위치라면

이미 반복했던 위치기에 다시 곰팡이를 그릴 이유가 없다.

하지만 해당 문제는 쉽게 지나칠수 있는 문제가 존재한다.

바로 마지막줄인 "만약 곰팡이가 증식해야 하는 부분이 벽으로 막혀 있다면, 그곳으로는 증식하지 못한다."

해당 문제에서 증식 하지못한다면 자연적으로 사라진다.

곰곰히 생각해보면 3*3의 가운데 지점 에서만 문제가 될수있다.

그 미만(2*2 ,1*1)에서는 곰팡이는 생존이 불가능하고

초과되었을때는 어느 장소에 생겨도 한무반복은 예정되어있다.

예외 예제를 보자 

해당위치는 3*3이상에서 의 유일한 사라지는 위치다. 이부분만 조심해서 문제를 풀자.

프로그램의 입력은 표준 입력으로 받는다. 첫 줄에 영우의 방의 크기, 방에 있는 곰팡이의 개수, 청소 검사 시스템이 검사하는 방바닥 좌표의 개수, 청소 검사가 실시 되기까지 남은 일수인 N M K t 가 주어진다.

(1 ≤ N ≤ 300, 0 ≤ M ≤ N2, 0 ≤ K ≤ N2, 1 ≤ t ≤ 10000)

둘째 줄부터 M 개의 줄에 걸쳐 영우의 방에 있는 곰팡이의 위치인 Mx My가 주어진다.(1 ≤ Mx, My ≤ N)

다음 줄부터 K 개의 줄에 걸쳐 검사관이 검사하는 방바닥의 위치인 Kx Ky가 주어진다.(1 ≤ Kx, Ky ≤ N)

N 영우의 방크기

M 방에있는 곰팡이의 개수

K 검사하는 방바닥 좌표의개수

t  청소 검사가 실시 되기까지 남은 일수

5 2 4 1

2 1

3 3

3 1

3 2

3 3

3 4

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void ClearRoom() {

	int N, M, K, t;
	cin >> N >> M >> K >> t;
	std::vector<vector<bool>> vmap(N + 1, vector<bool>(N + 1, false)),
		avmap(N + 1, vector<bool>(N + 1, false)),
		* Nextpm, * Dpm;
	std::queue <int> QSearchX;
	std::queue <int> QSearchY;


	int x = 0, y = 0;
	for (int i = 0; i < M; i++)
	{
		cin >> x >> y;
		vmap[--x][--y] = true;
		QSearchX.push(x);
		QSearchY.push(y);
	}

	const int dy[8] = { -1,-2,-2,-1,1,2,2,1 };
	const int dx[8] = { -2,-1,1,2,2,1,-1,-2 };
	for (int i = 0; i < t; ++i) {

		int Qsize = QSearchX.size();
        
        //오늘 방과 내일 영우의 방
		Dpm = &(((i % 2) != 0) ? avmap : vmap);
		Nextpm = &(((i % 2) == 0) ? avmap : vmap);
		//현재 일수에 움직이는 곰팡이
        for (int j = 0; j < Qsize; j++)
		{
			int datax = QSearchX.front();
			int datay = QSearchY.front();
			QSearchX.pop();
			QSearchY.pop();
			bool check = false;
            
            //8방향 곰팡이 번식
			for (int i = 0; i < 8; ++i) {
				x = datax + dx[i];
				y = datay + dy[i];
				
                //곰팡이 가 번식 가능한지 확인후 번식
                if ((x < N && x >= 0 && y < N && y >= 0) && !(*Nextpm)[x][y])
				{
                	(*Nextpm)[x][y] = true;
                    // 다음 번식 예정인 queue
					QSearchX.push(x);
					QSearchY.push(y);
					check = true;
				}
			}
            //만약 해당 곰팡이가 어느 하나도 이동하지 못햇더라면
            //이 곰팡이는 다음날 죽는다.
			if (!check) {
				(*Dpm)[datax][datay] = false;
			}
		}
	}
	bool IsClear = false;
	Dpm = &(((t % 2) != 0) ? avmap : vmap);
    
    //검수의 날
	for (int i = 0; i < K; i++)
	{
		cin >> x >> y;
		if ((*Dpm)[x-1][y-1])IsClear = true;
		if (IsClear)break;
	}
	cout << (IsClear ? "YES" : "NO");
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	ClearRoom();
}

해당 문제를 풀며 

배열 문제의 1입력 과 0입력을 확실하게 잡아야했고

 또한 문제 t의 정의에 대해 확실하게 잡아야했다.

아래 시뮬레이터로 문제의 경우의 수를 확인해보자

영우가 빠른시일 내로 청소하지 않는다면 집은 곰팡이에게 잠식당해 버릴지도 모른다.

내가 이해한 위상정렬을 간단하게 정리해 보겠다.

위상정렬은 순환하지 않는  비순환 방향 그래프 에서만 가능하다.

https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC

위상정렬의 구현방법은 정말 간단한 순서로 알수있다.

1. 자신을 가리키는 간선이  없는 노드 들을  큐에 넣어준다.

2. 큐에 있는 노드를 받아준다.

3. 노드가 가리키는 간선을 지워준다.

 반복

위상정렬의 경우

순서가 얼마든지 바뀔수있다. 예를들면

위의 경우 1,3,2,5,4 일수있지만 

2번 노드의 간선을 지운뒤 5와 4는 얼마든지 바뀔수 있다.

따라서 정답은 13254 와 13245 31245  31254 가 될수있다.

여기서 보이는 특징은

13 은 바뀔수 있지만  {13},{ 2} ,{ 54 }는 서로 바뀌지않는다.

만약 위의 예시로  작은순으로 모아야 하는경우

13 2 54 가 나온다. 이러한 문제는 

백준 : 문제집 1766번  정답비율 48.903% 문제에서 접할수있다. 

	//노드 간선수
    int a = 0, b = 0;
	cin >> a >> b;
	
    // 노드를 담을 queue
    queue<int> q;
	// v =  자신을 가리키는 간선 수
    vector<int> v(a + 1);
    // va = 배열로 만든 그래프
	vector<vector<int>> va(a + 1);
    
	vector<int>answer;
    
    
	int x = 0, y = 0;
	for (int i = 1; i <= b; i++) {
		cin >> x >> y;
        //그래프 추가
		va[x].push_back(y);
		// 간선 수 추가
        ++v[y];
	}
    
    //가리키는 간선이 없는 노드 큐에 추가
	for (int i = 1; i < v.size(); i++) {
		if (v[i] == 0) {
			q.push(i);
		}

	}
    
    
    // 큐에 노드가 없을때까지 반복
    //만약 큐에 노드가 없지만 모든 노드를 확인하지 않은경우 사이클이 존재함
	while (!q.empty())
	{
    // v_n 노드 번호
		int v_n = q.front();
		q.pop();
        
		cout << v_n<<"\n";
		
        //노드 가 가리키는 노드들
        for (auto i : va[v_n]) {
            //간선수 지워주기
			v[i]--;
            
            //만약 지워준 노드를 가리키는 간선이 더이상 없을경우 queue에 추가
			if (v[i] == 0) {
				q.push(i);
			}
		}
	}

위상정렬 백준 문제

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

 
처음 풀어보는 백준의 플래티넘 문제.
 
내가 풀었던 방식 부터 적을 생각이다.
 
우선 문제는 이름 그대로 최단 경로가 아닌 거의 최단 경로를 찾는다.
그래프에서 최단경로들의 간선을 제외한 그다음에 나오는 최단경로를 찾는 문제
 
우선 생각했던 방법은 다익스트라로 간선들을 지우면서 나간뒤 다익스트라를 한번더 돌릴예정이였다.
 
그렇게 테스트 하였지만 결과는 8% 실패
 
 
 
실패 이유는 다익스트라로 간선을 지울경우 간선이 하나만 지워지는 문제가 생긴다.
 

 
위 의경우  최단경로는 두개로   1 2 4 5 와  1 3 4 5가 있다.
 
거의 최단경로는 저두개를 제외한 1 ->5인  이여야 하지만
 
경로를 먼저 지워주게 될경우 4->5가 공유되지않으면서
거의최단경로는 6이 나오게된다. 
 

 
정상적인경우 위처럼 최단경로들을 제외하여 4->5로가는 길을 쓸수없기에  7이 나오지 못한다.
 
 
두번째 아이디어는 지나가면서 모든 지나온 간선  1->2 일경우 tuple<1,2> 식으로 queue 에 담아간뒤
 

마지막 칸에 도착하였을경우 최적해로 도착한 queue내부의 간선중 지워지지 않은 간선을 지워주었다.
 
문제에서 실패는 없었지만 25%에서 메모리 초과가 났다.
 
 
 
 
여기서 한동안 고민을 하다. 문제를 알아냈다.
 
문제는 메모리 초과 
 
queue로 간선을 담으면서 갈경우 특정 노드에서 만나는경우 왔던 간선을 유지하기위해
최단거리가 두개가 같은노드에서 만나면 둘다 큐에 넣어주었다.

 
위 같이 이런경우 같은 노드에 만나는 경우 이후 노드의 값만큼 의미없는 계산이 기하급수적으로 늘어날수 있다.
이후 계산은 전부 똑같지만 일전의 계산때문에 그전 간선이 다른 만큼 계산이 늘어남
 
 
 
 
문제를 해결하기위해 코드를 크게 변경해주었다.
 
우선 다익스트라를 돌며 같은 중간노드에서 같은 값이 있을경우 를 해결하기위해
 
다익스트라에서  현재위치의 크기를 알아야 한다.
그뒤 현재 노드로 온 그전 노드의 위치를 알수있어야 한다.
 

이렇게 만든경우
최소 큐 에서  더큰 같은 크기의 거리에서 만난 경우 그냥 그 위치에 왔던 노드를 표시해준다면
도착한뒤 돌아가면서 간선 제거를 해준다면

위 이미지 처럼 
다익 두번 과 간선 지우는 bfs한번만에 해결가능하다.

아래는 해결코드다.

#include<queue>
#include <unordered_map>
#include<vector>
#include<iostream>

using namespace std;

#define cost 0
#define Nextroad 1

// 매직넘버
#define MM_Num  9999999


const auto& mt = make_tuple(MM_Num, MM_Num);

//간선을 확인하며 삭제하는 함수
void Distory(unordered_map<int, vector<tuple<int, int>>>& Umap, vector< queue<int>>& nodeGansun, int end) {
	//도착지점에서 돌아가면서 왔던길 삭제
	while (!nodeGansun[end].empty())
	{
		int num = nodeGansun[end].front();
		nodeGansun[end].pop();
		for (auto& um : Umap[num]) {
			if (get<1>(um) == end) {
				um = make_tuple(MM_Num, MM_Num);
				Distory(Umap, nodeGansun, num);
			}
		}
	}
}
//간선을 기록하며 가는 다익스트라
void find_FIRST_DS(unordered_map<int, vector<tuple<int, int>>>& Umap, int start, int end, int nodesize) {
	priority_queue<tuple<int, int, int>> nextxy;
	vector<int> noodBool(nodesize + 1, MM_Num);
	vector< queue<int>>nodeGansun(nodesize + 1, queue<int>());
	noodBool[start] = MM_Num;

	tuple<int, int, int> nxy;
	int d = 0, arrowRoad = 0, arrowcost = 0;
	nextxy.emplace(make_tuple(0, start, start));

	int first = MM_Num;
	while (!nextxy.empty())
	{
    	

		nxy = nextxy.top();
		nextxy.pop();
		arrowcost = -get<0>(nxy);
		arrowRoad = get<1>(nxy);
        
		if (get<1>(nxy) == end) {
			if (first == get<0>(nxy)) {
				first = get<0>(nxy);
				break;
			}
		}
        //최단거리 이며 다른 간선을 통해 하나의 노드에 도착했을경우
        // 이전의 노드 를 현재 노드에 저장
		if (noodBool[arrowRoad] == MM_Num || noodBool[arrowRoad] > (arrowcost)) {
			noodBool[arrowRoad] = arrowcost;
			nodeGansun[arrowRoad] = queue<int>();
			nodeGansun[arrowRoad].push(get<2>(nxy));
		}
		else if (noodBool[arrowRoad] == (arrowcost))
		{
			nodeGansun[arrowRoad].push(get<2>(nxy));
			continue;
		}
		else  continue;
		d = get<0>(nxy);
		for (int i = 0; i < Umap[get<Nextroad>(nxy)].size(); ++i) {

			tuple<int, int> arrow = Umap[get<1>(nxy)][i];
			arrowRoad = get<1>(arrow);
			arrowcost = get<0>(arrow);
			if (noodBool[arrowRoad] == MM_Num || noodBool[arrowRoad] > (arrowcost + -(d))) {
				nextxy.emplace(make_tuple(-(arrowcost + -(d)), get<1>(arrow), get<1>(nxy)));
			}
		}
	}
	while (!nextxy.empty()) {
		auto b = nextxy.top();
		nextxy.pop();
		if (get<1>(b) == end && get<0>(b) == first) {
			nodeGansun[end].push(get<2>(b));
		}
	}
	Distory(Umap, nodeGansun, end);
	return;
}
//그냥 다익스트라
int find_second_DS(unordered_map<int, vector<tuple<int, int>>>& Umap, int start, int end, int nodesize) {
	priority_queue<tuple< int, int>> nextxy;
	vector<bool> noodBool(nodesize + 1, false);
	tuple<int, int> nxy;
	nextxy.emplace(make_tuple(0, start));
	bool lastnode = false;
	noodBool[start] = true;
    
    //다음 갈 장소가 없으면 끝냄
	while (!nextxy.empty())
	{
		nxy = nextxy.top();
		nextxy.pop();
        온길 기록
		noodBool[get<1>(nxy)] = true;
		//도착지에 도착하면 최단거리 리턴
		if (get<1>(nxy) == end) {
			return  (-get<0>(nxy));
		}
        
		for (const auto& arrow : (Umap[get<1>(nxy)])) {
			//현재 간선에서  갈수있는 간선들 이동
            
            //만약 지워진 간선일경우 
        	if (get<1>(arrow) == MM_Num)continue;
            // 이미 왔던 간선일경우 
			if (noodBool[get<1>(arrow)]) {
				continue;
			}
            // 다음간선 + 이동값 queue 추가
			nextxy.emplace(make_tuple(-(get<0>(arrow) + -(get<0>(nxy))), get<1>(arrow)));
		}
	}
	return (-1);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin.tie(NULL);
    
	int NodeSize = 0, NodeLoadSize = 0, Start = 0, end = 0;
	int node = 0, Xnode = 0, Dis = 0;
	
    unordered_map<int, vector<tuple<int, int>>> Umap;
	vector<int> answer;
	
    while (true)
	{
		cin >> NodeSize >> NodeLoadSize;
		if (NodeSize == 0 && NodeLoadSize == 0)
			break;
		cin >> Start >> end;

		Umap.clear();
		for (int i = 0; i < NodeLoadSize; i++)
		{
			cin >> node >> Xnode >> Dis;
			Umap[node].emplace_back(make_tuple(Dis, Xnode));
		}
		
		find_FIRST_DS(Umap, Start, end, NodeSize);
		answer.emplace_back(find_second_DS(Umap, Start, end, NodeSize));
	}
	for (const auto& an : answer) {
		printf("%d\n", an);
	}
	return 0;
}