BZOJ1003: [ZJOI2006] 물류운송trans(DP)

5964 단어 dp
전송문액, 이 문제를 받은 후에 나무랄 생각은 없었고...DP의 어느 쪽으로든 가지 않았다. (제목이 적고 사람이 너무 멍청하다...) 그래서 디스커스를 몰래 봤는데 상태 이동 방정식을 보고 문득 깨달았다.f(i)=f(j)+dis(j+1, i)∗(i-j)+K 그중(0<=j/************************************************************** Problem: 1003 User: geng4512 Language: C++ Result: Accepted Time:40 ms Memory:948 kb ****************************************************************/ #include<cstdio> #include<algorithm> #include<queue> #include<cstring> #define LL long long using namespace std; int dis[150][150], n, m, e, D, K; #define MAXN 30 #define MAXM 900 struct node { int v, w; node *nxt; }Edge[MAXM], *Adj[MAXN], *Mcnt = Edge; void Addedge(int u, int v, int w) { node *t = ++ Mcnt; t->v = v; t->w = w; t->nxt = Adj[u]; Adj[u] = t; } bool inq[MAXN]; int au[MAXN][105]; int d[MAXN]; LL f[MAXN]; void spfa(int S, int b, int e) { memset(d, 0x3f, sizeof d); queue<int> q; int u, v; d[S] = 0; q.push(S); while(!q.empty()) { u = q.front(); inq[u] = 0; q.pop(); for(node *p = Adj[u]; p; p = p->nxt) { v = p->v; if(au[v][e] - au[v][b-1] > 0) continue; if(d[v] > d[u] + p->w) { d[v] = d[u] + p->w; if(!inq[v]) { q.push(v); inq[v] = 1; } } } } dis[b][e] = d[m]; } void Fill(int u, int s, int e) { for(int i = s; i <= e; i ++) au[u][i] = 1; } int main() { int u, v, w; scanf("%d%d%d%d", &n, &m, &K, &e); for(int i = 1; i <= e; i ++) { scanf("%d%d%d", &u, &v, &w); Addedge(u, v, w); Addedge(v, u, w); } scanf("%d", &D); for(int i = 1; i <= D; i ++) { scanf("%d%d%d", &u, &v, &w); Fill(u, v, w); } for(int i = 1; i <= m; i ++) for(int j = 1; j <= n; j ++) au[i][j] += au[i][j-1]; for(int i = 1; i <= n; i ++) { for(int j = i; j <= n; j ++) spfa(1, i, j); } f[0] = -K; for(int i = 1; i <= n; i ++) { f[i] = 0x3f3f3f3f; for(int j = 0; j < i; j ++) f[i] = min(f[i], f[j] + 1LL*dis[j+1][i]*(i-j) + K); } printf("%d", f[n]); return 0; }

좋은 웹페이지 즐겨찾기