URAL 1741 Communication Fiend dp

제목 링크: 클릭 하여 링크 열기

#include <cstdio>
#include <algorithm>
#include <cstring>
typedef long long ll;
const ll Inf = (ll)(1e15);
const int N = 10000 + 10;
const int E = 10000 + 10;
struct Edge {
	int v, cos, f, nex;
	Edge() {
	}
	Edge(int _v, int _cos, int _f, int _nex) {
		v = _v;
		cos = _cos;
		f = _f;
		nex = _nex;
	}
};

int g[N], idx;
Edge eg[E];

ll d[N][2];
int n, m;

void addedge(int u, int v, int len, int f) {
	eg[idx] = Edge(v, len, f, g[u]);
	g[u] = idx++;
}

ll dp(int dep, int fl) {
	if (d[dep][fl] >= 0)
		return d[dep][fl];
	d[dep][fl] = Inf;
	int to;
	for (int i = g[dep]; ~i; i = eg[i].nex) {
		to = eg[i].v;
		if (eg[i].f == 0) {
			d[dep][fl] = std::min(d[dep][fl], dp(to, 1) + eg[i].cos);
		} else if (eg[i].f == 1) {
			if (fl)
				continue;
			d[dep][fl] = std::min(d[dep][fl], dp(to, 0) + eg[i].cos);
			d[dep][fl] = std::min(d[dep][fl], dp(to, 1) + eg[i].cos);
		} else if (eg[i].f == 2) {
			d[dep][fl] = std::min(d[dep][fl], dp(to, fl) + eg[i].cos);
		}
	}
	return d[dep][fl];
}

void work() {
	int u, v, cos;
	char s[15];
	ll ans;
	
	idx = 0;
	memset(g, -1, sizeof g);
	while (m -- > 0) {
		scanf("%d%d%d%s", &u, &v, &cos, s);
		if (*s == 'L') {
			addedge(v, u, cos, 0);
		} else if (*s == 'P') {
			addedge(v, u, cos, 1);
		} else {
			addedge(v, u, cos, 2);
		}
	}
	
	memset(d, -1, sizeof d);
	d[1][1] = 0;
	ans = std::min(dp(n, 1), dp(n, 0));
	if (ans == Inf)
		puts("Offline");
	else {
		puts("Online");
		printf("%I64d
", ans);
	}
}
int main() {
	while (~scanf("%d%d", &n, &m))
		work();
	return 0;
}