11657번-타임머신

문제

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

11657번: 타임머신

---

접근방법

1) 접근 사고

 

2) 시간 복잡도

 

3) 배운 점

 

4) PS

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 501;
int n, m;
vector<pair<int,int>> edge[MAX];
ll dist[MAX];
int main(void)
{
    fastio;
    cin >> n >> m;
 
    for(int i =0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edge[a - 1].push_back({c, b - 1});
    }
 
    bool cycleFlag = false;
    fill(dist, dist + n, INT_MAX);
    dist[0] = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(auto cur : edge[j])
            {
                int neighborCost = cur.first;
                int neighbor = cur.second;
                if(dist[j] != INT_MAX && dist[neighbor] > neighborCost + dist[j])
                {
                    dist[neighbor] = neighborCost + dist[j];
                    if(i == n -1)
                        cycleFlag = true;
                }
            }
        }
    }
 
    if(cycleFlag)
        cout << -1 <<"\n";
    else
    {
        for(int i = 1; i < n; i++)
        {
            if(dist[i] != INT_MAX)
                cout << dist[i] <<"\n";
            else
                cout << -1 << "\n";
        }
    }
}