백준 2637 장난감 조립 (C++)

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

2637번: 장난감 조립

 

갑자기 #define 이랑 typedef랑 헷갈렸다.. 

long long으로 완전 다 바꾸어 버렸는데 

int의 범위가

-2,147,483,648 ~ 2,147,483,647

 

long long은 

-9,223,372,036,854,775,808 to 9,223,372,036,854,775,807

 

이므로 사실 int형을 써도 괜찮을것 같다. 괜히 큰 숫자 보고 long long으로 썼긴 하지만 이 기회에 int 범위를 정확하게 알고 가야겠다.  

#include <iostream>
#include <vector>
#include<queue>
#include<map>

typedef long long ll;

using namespace std;


int n, m;
vector<ll>indegree;
vector<vector<pair<ll, ll>>>graph;
vector<ll>arr;
vector<vector<ll>>dp;
ll N;

map<ll, ll>defaults;
void tpsort() {

	queue<ll>q;

	for (ll i = 1; i <= N; i++) {
		if (indegree[i] == 0) {
			q.push(i);
			dp[i][i] = 1;
			defaults[i] = 1;
		}
	}

	while(!q.empty()) {
		
		ll p = q.front();
		arr.push_back(p);
		q.pop();

		for (ll i = 0; i < graph[p].size(); i++) { // x만드는데 k개 
			ll x = graph[p][i].first;
			ll k = graph[p][i].second;
			indegree[x]--; 
			for (ll j = 1; j <= N; j++) {
				dp[x][j] += (dp[p][j]*k);
			}
			if (indegree[x] == 0)q.push(x);
	
		}
	}

}



int main() {

	ll n,m;
	cin >> n; //완제품 번호  
	N=n;
	indegree.assign(n+1, 0);
	graph.assign(n + 1, vector<pair<ll, ll>>());
	dp.assign(n + 1, vector<ll>(n+1,0));

	cin >> m;
	
	ll x, y, k;
	for (ll i = 0; i < m; i++) {
		cin >> x >> y >> k; //x만드는데 y가 k가 필요 
		indegree[x]++; 
		graph[y].push_back({ x,k });
	}

	tpsort();
	
	for (ll i = 1; i <= n; i++) {
		if (defaults[i])cout << i <<' '<< dp[n][i]<<'\n';
	}
}