이번 문제는 새로운 알고리즘 개념이 필요한 문제여서 많이 어려웠다. "최단 경로"인 것을 확인하고 다익스트라 알고리즘을 통해 해결해보고자 하였는데 경로가 양수 -> 음수 -> 도착
과 양수 -> 도착인 경우를 해결 하지 못해 결국 정답을 내지 못했는데 이를 Bellman Ford 알고리즘을 통해 해결 할 수 있다는 것을 알게 되었다. <-이해 출처

오답

#include <iostream>
#include <deque>
#include <string>
#include <vector>
#include "Algorithm.h"

using namespace std;
int tc, n, m, w, s, e, t;
int flag = 0;
vector<pair<int, int>> mi[200];
vector<pair<int, int>> pl[2500];

void input()
{
    cin >> tc;
    cin >> n >> m >> w;
    for (int i = 0; i < m; i++) {
        cout << "도로 입력" << endl;
        cin >> s >> e >> t;
        pl[s].push_back(make_pair(e, t));
        pl[e].push_back(make_pair(s, t));

    }

    for (int i = 0; i < w; i++) {
        cout << "웜홀 입력" << endl;
        cin >> s >> e >> t;
        mi[s].push_back(make_pair(e, t));
    }
    
}

void solve() {
    for (int i = 1; i <= n; i++) {
        deque<pair<int, int>> q;
        q.push_back(make_pair(i, 0));

        while (!q.empty()) {
            int point = q.front().first;
            int time = q.front().second;
            q.pop_front();
            if (pl[point].size() >= 1) {
                for (int i = 0; i < pl[point].size(); i++) {
                    int next_point = pl[point][i].first;
                    int next_time = pl[point][i].second;
                    cout << next_time << " " << time + next_time << " " << " pl 실행" << endl;
                    q.push_back(make_pair(next_point, time + next_time));
                }
            }
            if (mi[point].size() >= 1) {
                for (int i = 0; i < mi[point].size(); i++) {
                    int next_point = mi[point][i].first;
                    int next_time = mi[point][i].second;
                    cout << next_time << " " << time - next_time << " " << " mi 실행" << endl;
                    q.push_back(make_pair(next_point, time - next_time));
                }
            }

        }
        
        int result = q.front().second;
        if (result <= 1) {
            flag = 0;
        }
        else {
            flag = 2;
        }

    }
}

void answer()
{
    if (flag == 0) {
        cout << "YES" << "\n";
    }
    else {
        cout << "NO" << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    input();
    solve();
    answer();
}

정답 코드 출처

#include<iostream>
#include<vector>
#include<cstring>
#include<string>
 
#define endl "\n"
#define MAX 510
#define INF 987654321
using namespace std;
 
int N, M, W;
int Dist[MAX];
string Answer;
vector<pair<pair<int, int>, int>> Edge;
 
void Initialize()
{
    for (int i = 1; i < MAX; i++) Dist[i] = INF;
    memset(Dist, -1, sizeof(Dist));
    Edge.clear();
}
 
void Input()
{
    cin >> N >> M >> W;
    for (int i = 0; i < M; i++)
    {
        int From, To, Cost;
        cin >> From >> To >> Cost;
        Edge.push_back(make_pair(make_pair(From, To), Cost));
        Edge.push_back(make_pair(make_pair(To, From), Cost));
    }
    for (int i = 0; i < W; i++)
    {
        int From, To, Cost;
        cin >> From >> To >> Cost;
        Edge.push_back(make_pair(make_pair(From, To), -Cost));
    }
}
 
void Solution()
{
    Dist[1] = 0;
    for (int i = 1; i <= N - 1; i++)
    {
        for (int j = 0; j < Edge.size(); j++)
        {
            int From = Edge[j].first.first;
            int To = Edge[j].first.second;
            int Cost = Edge[j].second;
 
            if (Dist[From] == INF) continue;
            if (Dist[To] > Dist[From] + Cost) Dist[To] = Dist[From] + Cost;
        }
    }
    for (int i = 0; i < Edge.size(); i++)
    {
        int From = Edge[i].first.first;
        int To = Edge[i].first.second;
        int Cost = Edge[i].second;
 
        if (Dist[From] == INF) continue;
        if (Dist[To] > Dist[From] + Cost)
        {
            Answer = "YES";
            return;
        }
    }
    Answer = "NO";
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
        cout << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}