백준(BOJ) 16167 A Great Way *

# DP

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string.h>
#include <string>
#include <set>
#include <climits>
#include <stack>
#include <functional> 
#include <map>
#define INF 987654321
#define EPS 0.000001
#define MOD 100003
using namespace std;
typedef pair<int, int> pa;
typedef long long ll;
typedef pair<ll, ll> llpa;

int n, r;
vector<pa> link[110];
int a, b, c, d, e;
pa dp[110];

int main() {
	scanf("%d %d", &n, &r);
	for (int i = 0; i < r; i++) {
		scanf("%d %d %d %d %d", &a, &b, &c, &d, &e);
		int now = c;
		if (e > 10) {
			e -= 10;
			now += e*d;
		}
		link[a].push_back({ b, now });
	}
	memset(dp, -1, sizeof(dp));
	dp[1] = { 0, 1 };
	deque<int>dq;
	dq.push_back(1);
	while (!dq.empty()) {
		int now = dq.front();
		dq.pop_front();
		for (pa next : link[now]) {
			if (dp[next.first].first == -1 ||
				dp[next.first].first > dp[now].first + next.second ||
				dp[next.first].first == dp[now].first + next.second && dp[next.first].second > dp[now].second) {
				dp[next.first].first = dp[now].first + next.second;
				dp[next.first].second = dp[now].second + 1;
				dq.push_back(next.first);
			}
		}
	}
	if (dp[n].first == -1) {
		printf("It is not a great way.\n");
	}
	else {
		printf("%d %d\n", dp[n].first, dp[n].second);
	}
}