class BuildingHeights {
public:
int minimum(vector h) {
int n = h.size();
vector d(n+1, INF);
d[0] = 0;
for (int k = 1; k <= 4000; k++) {
vector b;
for (int i = 0; i < n; i++)
if (h[i] <= k) b.push_back(k-h[i]);
sort(b.begin(), b.end());
int cur = 0;
for (int i = 1; i <= b.size(); i++) {
cur += b[i-1];
d[i] = min(d[i], cur);
}
}
int ans = 0;
for (int i = 1; i <= n; i++) ans ^= d[i];
return ans;
}
};
450: 나는 Dijkstra 한번 돌려서 Shortest Path의 edge만 남겨서 DAG를 만든 다음 위상정렬하면서 DP를 채웠는데(답이 -1인경우는 이 DAG에 가중치 0인게 있는 경우 뿐), 알고보니 그냥 Dijkstra 하면서 DP배열을 같이 채우면 되는거였다.
#define x first
#define y second
typedef pair< int, int > ii;
vector v[2001];
vector p[2001];
vector e[2001];
vector road;
vector d;
vector vis;
int cost[2001][2001];
const int INF(1<<27);
void Find(int x) {
if (vis[x]) return;
vis[x] = 1;
for (int i = 0; i < p[x].size(); i++) {
e[p[x][i]].push_back(x);
road.push_back(ii(p[x][i], x));
Find(p[x][i]);
}
}
class DrivingPlans {
public:
int count(int n, vector aa, vector bb, vector cc) {
vis.resize(2001, false);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
cost[i][j] = 500000;
}
for (int i = 0; i < aa.size(); i++) {
v[aa[i]].push_back(bb[i]);
v[bb[i]].push_back(aa[i]);
cost[aa[i]][bb[i]] = cc[i];
cost[bb[i]][aa[i]] = cc[i];
}
d.resize(n+1, INF);
priority_queue< ii, vector, greater > q;
q.push(ii(0, 1));
d[1] = 0;
while (!q.empty()) {
ii now = q.top(); q.pop();
if (d[now.y] < now.x) continue;
for (int i = 0; i < v[now.y].size(); i++) {
int nv = v[now.y][i],
nd = now.x + cost[now.y][nv];
if (nd < d[nv]) {
d[nv] = nd;
p[nv].clear();
p[nv].push_back(now.y);
q.push(ii(nd, nv));
} else if (nd == d[nv]) {
p[nv].push_back(now.y);
}
}
}
Find(n);
vector in(n+1, 0);
for (int i = 0; i < road.size(); i++){
int from = road[i].x,
to = road[i].y;
++in[to];
if (cost[from][to] == 0) return -1;
}
queue s;
int dy[2001] = {0, 1};
int ans = 0;
const int MOD(1000000009);
for (int i = 1; i <= n; i++) {
if (!in[i]) s.push(i);
}
while (!s.empty()) {
int now = s.front(); s.pop();
for (int i = 0; i < e[now].size(); i++) {
int nv = e[now][i];
dy[nv] += dy[now];
if (dy[nv] >= MOD) dy[nv] -= MOD;
if (--in[nv] == 0) {
s.push(nv);
}
}
}
return dy[n];
}
};