부분합은 특정 구간의 합을 효율적으로 계산하기 위해 누적합을 활용하는 방법이다.

입력할때 전부 더해두고 이후에 재사용한다는 계념이다.

그래서 최소 한번이상 사용해야 이득이다.

1차원배열은 

 index = [1]   [2]    [3]   [4]    [5]      [6] 이 있다

 DP =    [1]   [3]    [6]   [10]   [15]   [21] 배열을 만들어준뒤

배열은 이전값에서 M을 더한 값   [N]= [N-1] + M

3번부터5번값 을 구해야 한다면?

아래처럼 3 부터 5까지 index를 하나씩 올리며 구해도 괜찮다. 

 [1]   [2]   [3]   [4]    [5]      [6]

 1      2     3     4      5        6

                3      4     5

                       12

DP 배열 에서 구하는법은 아래와 같다

우선 쉽게 위치로 보자면  

1       3       6 10 15       21

1       2       3~~~5`

포함되어있지않은 x-1 를 찾아준다

            [3]     [6]     [15]
          [x-1]              [ y]

비포함인부분을 포함되어있는 부분에서 빼주면 

            [y]  -  [x-1] 

           15  - 3    =   12

2차원행렬은 

기본적인 아이디어가 똑같기에 더해준뒤 중복값 제거 

그렇다면 x1,y1   x2, y2 를 계산할땐 어떤식으로 계산해야할까

위와 같은 행렬 에서 해당파란  0,0   1,1  부분을 구하고싶다면

그냥 1,1 부분을 출력해도 무방할것이다.

그렇다면

같은 부분을 구하려면 어떻게 해야할까

이것도 1차원 행렬 과 같은방식이다.

아래는 DP 행열이다

우선 전체 합인 22  

그리고 제외할부분인 6 과 6 을 빼준다

그러면 6에는공통적으로 들어가게 되는 1이 두번 빠지게 된다.

그럼으로 공통적으로 빠지는 1을 더해주면  구역값이 나오게 된다.

22 - 6 - 6 +1

이걸 펼쳐본다면

전체 크기에 빠진크기만큼 세로 가로를 빼준뒤 중복되어있는부분을 다시 더해주면 완성!

행렬  옆 0 줄이 있는건 계산을 쉽게 하기 위해서다.

아래 구현 코드와 계산기로 쉽게 확인해보자

	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);


	int N, M;
	cin >> N >> M;
	int mix_n = N, mix_m = N;
	vector<vector<int>> vmap(mix_n + 1, vector<int>(mix_m + 1, 0));
	for (int i = 1; i < mix_n + 1; i++)
	{
		for (int j = 1; j < mix_m + 1; j++)
		{
			int k = 0;
			cin >> k;
			vmap[i][j] = k + vmap[i - 1][j] + vmap[i][j - 1] - vmap[i - 1][j - 1];
		}
	}
	for (int i = 0; i < M; i++) {
		int Lx, Ly, Rx, Ry;
		cin >> Lx >> Ly >> Rx >> Ry;
		int mixAnswer = vmap[Lx - 1][Ly - 1] + vmap[Rx][Ry] - vmap[Rx ][Ly - 1] - vmap[Lx - 1][Ry ];
		cout << mixAnswer<<"\n";
	}

유니티에는 단축키를 쉽게 확인하고 단축키를 지정할수 있는 기능이 있다.

게임엔진 답게 다른 프로그램보다 확인하기 쉽게 되어있다.

너무 간단한 기능이기에 이런게 있구나 하고  어떤 단축키들이 할당되어있는지 보고 넘어가도 좋다.

한번 보도록 하자.

우선 Shortcuts을 키는 법은 Edit -> Shortcuts.. 에서 확인할수 있다.

누르면 창이 하나 켜진다.

아래와 같은 창이 켜지는 것을 확인할수있다.

키에 마우스를 올리면 어떠한 단축키가 할당되어있는지 확인할수있다.

색마다 다른데

유니티에는 단축키를 쉽게 확인하고 단축키를 지정할수 있는 기능이 있다.

게임엔진 답게 다른 프로그램보다 확인하기 쉽게 되어있다.

한번 보도록 하자.

우선 쇼우올컷 을 키는 법은 Edit -> Shortcuts..

아래와 같은 창이 켜지는 것을 확인할수있다.

초록색 네모칸은 현재 할당되어 있는 키를 확인할수있는데.

마우스를 올리면 어떤 기능이 할당되어있는지 알수있다.

설명이 버전마다 살짝식 차이가 있는데.

우선 유니티 공식 문서에선 아래와 같이 설명하고있다.

하지만  직접 캡쳐한 버전에선

위에 설명으로 

보라색 키 역시 mixed key 로 색이 다르게 추가되어있다.

마우스를 올리고 기다리면 할당되어있는 단축키를 보여준다

우클릭시

지우거나 기본설정으로 초기화 할수있으며

특수키 를 키보드로 누르거나 마우스로 누르면 

연계되어있는 숏컷만 확인도 가능하다.

또한 단축키 세팅을 새로만들거나 저장, 불러오기 가 가능하다.  

마지막으로 아래와 같이  숏컷의 종류들을 전부 확인가능하다.

할당안되어있는 것들은 눌러서 단축키를 넣어줄수있다.

아래와같이  맨오른쪽의 숏컷 부분을 누른뒤 원하는 키를 눌렀다 때면 생성할수있고.

사용할수있다.

여기서도 우클릭하면 초기화 제거 를 할수있다.

https://school.programmers.co.kr/learn/courses/30/lessons/43164

BFS와 DFS 문제 레벨3 단계의 여행경로 문제다.

이해하는 데 확실히 오래 걸린 문제다



처음 생각은 그냥 DFS 문제인 줄 알고 알파벳 정렬 후 빠른 순으로 탐색하였다.
풀면 채점 시 1번 2번 실패, 3번 4번 성공한다.



생각해 낸 아이디어는
위 문구처럼 무조건 다 갈 수 있다는 이야기는


만약 끝까지 탐색 DFS를 했을 경우에도 모든 티켓(간선)을 사용하지 않았다면 그 간선은 마지막에 방문해야 하는 간선이다.


또한 같은 티켓이 두 개일 수 있다.





1. 그래프를 만들며 그래프를 알파벳순으로 정렬한다.
2. 그래프를 순서대로 탐색한다.
3. 더 이상 다른 노드로 이동할 수 없는 경우 사용한 티켓(간선)의 개수와 전체 티켓(간선)의 개수를 체크한다.
3.1달을 경우 이전 노드로 돌아간다.
4 만약 돌아왔으면 다음 2로 돌아가 다음 순서 노드를 탐색한다.

#include <string>
#include <vector>
#include <map>
#include <queue>
using namespace std;

int ticketSize = 0;
vector<string>Aanswer;
bool findAir(string start,int num,vector<string> answer, map<string, map<string, int>, greater<string>>ticketsmap) {


    //사용한 티켓 기록
    answer.push_back(s.first);

   //이동한 간선수와 전체 간선의 수 비교
    if (num == ticketSize) { Aanswer = answer; return true; }

   //정렬된 간선 순서대로 이동
    for (auto s : ticketsmap[start]) {

    //간선이 존재하는가 확인
        if (s.second >0) {
        // 티켓 갯수 빼기
            ticketsmap[start][s.first]--;
            //재귀함수 실행 
            if (findAir(s.first, num + 1, answer, ticketsmap) == true) 
            {
                //true 반환시 탈출
                return true; 
            }
            else {
                //만약 현재 티켓대로 갔을경우 전부 소진하지 못할경우
                //티켓을 사용하지 않은 상태로 원복 시킨다
                ticketsmap[start][s.first]++;
            }
        }
    }

    //간선을 전부 돌았지만 티켓을 전부 사용하지 못했을경우 false 반환
    answer.pop_back();
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {

    string start = "ICN";
    map<string, map<string, int>> ticketsmap;
    for (int i = 0; i < tickets.size(); ++i)
    {
    //티켓 그래프 제작
        ticketsmap[tickets[i][0]][tickets[i][1]]++;
        ticketSize += 1;
    }
    vector<string> answer = {};

    findAir(start,0, answer, ticketsmap);

    return Aanswer;
}

아래와 같이 확인할수 있다

틀린점이나 이상한점  질문 등이 있을경우 아래 댓글로 알려주시면 감사하겠습니다.

타잔 Tarjan

 타잔 알고리즘은 SCC 를 찾는 알고리즘이다.

SCC란?  (Strong Connection Component) 강결합 컴포넌트 

간단하게 서로 연결되어있는 순한 노드끼리 묶어준다고 생각하면 쉽다.

크게 두개의 알고리즘이 있다고 볼수있는데

코사라주 알고리즘과 타잔 알고리즘이다.

이번엔 타잔 알고리즘을 설명하려 한다.

맨 아래에는 pc로 접속시(모바일은 사용불가) 코드를 눈으로 보며 생각과 맞는지 확인해볼수 있으니

본문을 읽어본뒤 테스트를 해보자.

알고리즘의 큰틀을 먼저 이해하면 구현자체는 쉽게 할수있다.

타잔알고리즘의 순서는

우선 함수 전 

count = 노드번호와 상관없이 노드를 처음탐색했을경우  탐색 번호를 의미한다.

lowset[]       = ( count  ) 를 넣어두는 배열 이며 비교할때 쓰인다.  그래프의 노드 사이즈와 같은 크기를 가지고 있다.

visit[]           = 노드 의 초기 (노드 카운터)를 넣어두는 배열 

 Tarjan 알고리즘 함수를 정의한다. 
    1. 노드 카운터를 증가시키고 현재 노드를 방문한 것으로 표시한다.
    2. 현재 노드를 스택에 푸시한다.
    3. 현재 노드의 이웃을 반복하며 방문한다
        a. 이웃이 아직 방문되지 않았다면, 재귀적으로 Tarjan 알고리즘을 호출한다.
        b. 이웃이 scc가 이미 되어있을경우 다시 돌아온다.

        c. 이웃의 노드 카운트와 lowset(내부의 count ) 값 을 비교후 작은값을  lowset  에 업데이트한다.
    4. 만약 방문할 노드가 없고 lowset[node] 값 이 현재 visit[node] 와 같다면, 강한 연결 요소(SCC) 발견 되었다.:
        a. SCC를 저장할 임시 벡터를 만든다.
        b. 현재 노드에 도달할 때까지 스택에서 노드를 팝하고, SCC 저장.
        c. SCC 벡터를 주요 SCC 벡터에 추가합니다.

예시를 들어

아래와 같은 그래프가 존재한다.

DFS로 하나씩 하나씩 들어가본다면

1->2->3->4->5

stack 1,2,3,4,5

5까지 도착한뒤 5에서 다시 연결되어있던 4로 돌아간다

위 이미지 처럼 이동한뒤 4->5 다시 5에 연결되어있던 4로 이동 한다.  

4의 경우 이미 방문했던 노드이기때문에   

두개의 node count 를 비교해준다

4노드가 들고있는 count  4 
5노드가 들고있는 count  5

가장 작은 노드인 4를 가져온다.

그렇다면

node   [1][2][3][4]   [5]    [6]

count  [1][2][3][4][5 > 4][x]

4번 확인뒤 5번은 방문할 노드가 없기때문에 4번노드로 돌아온다(DFS)

4->6번노드 방문시 5 번 노드와 같이

node   [1][2][3][4][5]   [6]

count  [1][2][3][4][4][6 > 4]

이후  더이상 갈수있는 노드가 없다.

들고있는 lowset[node] 값과 현재의 노드visit[node]의  값이 같은경우

stack 을 현재 노드까지  빼준다

stack [1,2,3,4,5,6] 

         [1][2][3][4][5][6]
 num = 4

stack[1,2,3] 

scc[0] = {6,5,4}

scc 묶음이 생겼다 

stack  {1,2,3}

4에서 돌아온뒤 노드 3번을 마저 탐색한다.

노드 1방문(이미 방문했던 노드)=> 더 작은노드 1 < 3 = 1을반환한다. 

num  = 1

작은값 갱신후 3번 노드 에서 더이상 갈수있는 노드가 없다. 

더작은 값을 을 num에 넣으며 현재 node 와 비교해주며 1번 노드까지 리턴되어 돌아온다

그럼 num  =1 

stack[1,2,3]

1 까지 stack을 빼준다.

CSS{{6,5,4},{3,2,1}}

코드로 보도록 하자.

코드는 두가지로  준비를 해두었다. low 값을 vector 로 저장하는 방법과

먼저 보이는 코드는 위 설명처럼 배열을 사용한다.

그 아래 코드는 가장 작은 값을 전달하는 식으로 만들어진 코드다.

두개의 큰 틀은 비슷하니 두개다 보면 이해가 쉬울수있다.

코드 1 

class TarjanSCC {
public:
    TarjanSCC(int nodes) : n(nodes), index(0), sccCount(0) {
        visit.resize(n, -1);
        lowset.resize(n, -1);
        onStack.resize(n, false);
    }

    void addEdge(int from, int to) {
        graph[from].push_back(to);
    }

    vector<vector<int>> findSCCs() {
        for (int i = 0; i < n; ++i) {
            if (visit[i] == -1) {
                tarjan(i);
            }
        }
        return sccs;
    }

private:
    int tarjan(int v) {
        visit[v] = index;
        lowset[v] = index;
        index++;
        stackNode.push(v);
        onStack[v] = true;

        for (int w : graph[v]) {
            if (visit[w] == -1) {
                lowset[v] = min(lowset[v], tarjan(w));
            } else if (onStack[w]) {
                lowset[v] = min(lowset[v], visit[w]);
            }
        }

        if (lowset[v] == visit[v]) {
            vector<int> scc;
            int w;
            do {
                w = stackNode.top();
                stackNode.pop();
                onStack[w] = false;
                scc.push_back(w);
            } while (w != v);
            sccs.push_back(scc);
            sccCount++;
        }
        return lowset[v];
    }

    int n;
    int index;
    int sccCount;
    unordered_map<int, vector<int>> graph;
    vector<int> visit;
    vector<int> lowset;
    vector<bool> onStack;
    stack<int> stackNode;
    vector<vector<int>> sccs;
};

코드 2

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

stack<int> stackNode;
vector<bool> lowset;
vector<int> visit;
int nodecount = 0;
unordered_map<int, vector<int>> umap;
vector< vector<int>> scc;


int tajan(int index) {
	int num = 0;
	num = ++::nodecount;
	visit[index] = num;

	stackNode.push(index);
	for (int next : umap[index]) {
		if (visit[next] == -1) {
			num = min(tajan(next), num);
		}
		else if (lowset[next] == false) {
			num = min(visit[next], num);
		}
	}

	if (num == visit[index]) {
		vector<int> scc_temp;
		while (1) {
			int data = stackNode.top();
			stackNode.pop();
			lowset[data] = true;
			scc_temp.push_back(data);

			if (num == visit[data]) break;
		}
		sort(scc_temp.begin(), scc_temp.end());
		scc.push_back(scc_temp);
	}

	return num;
}

아래 시각화 도구로 확인해보자.

*그래프가 엉켜서 보기가 힘들다면*  클릭해서 노드 위치를 움직일수 있으니 보기 편하게 만든뒤 보면 보기 편하다

타잔 알고리즘 단계별 시각화 도구

원하는 도장, 스프레이 기능, 또는 자연스럽게 꾸미는 기능이 필요할경우

HDRP 유니티의 기능중 decal 기능을 사용할수있다

아래의 이미지 처럼  두개의 오브젝트에도 자연스럽게 위에 그릴수있다.

현재 사용한엔진은 2022.2.20f 버전의 데칼이다.

Component 에서 HDRP Decal Projector 을 추가해준다.

이전 기능에서는 projecter 으로 일반에서도 쓸수있던 기능이지만 HDRP 로 변경되었다.

우선  새로운 Material 을 생성해준다

shader을 decal로 선택하여준다

위처럼 이미지를 넣어준 머터리얼을  아까 추가해준 Decal Projector 의 material 에 넣어주면  끝이다.

아래와 같이 데칼의 경우 네모상자와 방향이 표시된다 방향에 맞게 비치할경우 이미지가 그려진다.

간단한 사용법을 알아봤으니 이제 내부 변수들을 확인해 보자

위의 3가지 이미지는 이미지로 보이는것처럼

DECAL을 조절하는  방식을 변경할수 있다.

Scale Move  : Scale Invariant , inherit from Hierachy  

Scale Invariant   :  아래의 Size , Depth Pivot 들만 사용하여 decal을 지정

 inherit from Hierachy    :  아래의 size Depth Pivot 들과 오브젝트의 Transform 의값도 포함하여 계산

Draw Distance : 카메라가 데칼을 렌더링하는 최대 거리

Tiling : uv 축을 따른 머터리얼의 Tiling 값

offset : uv 축을 따른 머터리얼의 offset  값

fade factor :  데칼의 투명도 조절 

Affects Transparent : 투명 포면위에 그릴수 있다.  Affect Transparenc가 활성화 되어있으면 

텍스처를 아틀라스에 패킹한다고 한다.

decal은 버전마다 조금씩 변수가 다르기에  아래의 주소에서 버전을 바꿔보면서 자신의 버전에 맞는 가이드를 읽어보는게 좋아보인다.

https://docs.unity3d.com/kr/Packages/com.unity.render-pipelines.high-definition@10.5/manual/Decal-Projector.html

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

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

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;
}