一个神奇的dp，，为数不多自己搞出来的dp。。。。
其实可以发现对于这个题， 单纯的最短路乱搞是错误的 那么，，，，dp 我们可以用cost[i][j] 表示从第i天到第j天的不换路花费， 当然算的时候保证这条路在i到j天都可以走， 那么是一定存在每个时间段不存在一条从起点到终点的道路的， 那么这个时候要判断一下赋值成+oo 我们再用dp[i] 表示前i天的总花费dp[i] = min{dp[j] + cost[j+1][i] + k| 0<=j< i};
那么由于我们在算第一天的时候多加了一个k， 那么结果减去一个k就好了
#include#include #include #include #include using namespace std;const int N = 200;const int M = 100*100;const int oo = 0x3f3f;#define next Next#define begin Begin#define rep(i, s, t) for(int i = s; i <= t; ++i)int d, t, n, m;long long k;int pd[N][N];struct node { int u, d; bool operator <(const node& rhs) const{ return d > rhs.d; }};struct dijkstra { long long f[N], cost[N][N], dis[N]; int vis[N]; int begin[N], to[M], next[M], w[M], e; void init() { e = 0; memset(begin, 0, sizeof(begin)); } void add(int x, int y, int z) { to[++e] = y; next[e] = begin[x]; w[e] = z; begin[x] = e; } void dij(int s, int S, int T) { memset(vis, 0, sizeof(vis)); priority_queue q; rep(i, 1, n) dis[i] = oo; dis[s] = 0; q.push((node) {s, dis[s]}); while(!q.empty()) { int u = q.top().u, v; q.pop(); if(vis[u]) continue; bool flag = false; rep(o, S, T) if(pd[u][o]) {flag = true; break;} if(flag) continue; vis[u] = 1; for(int i = begin[u]; i; i = next[i]) if(dis[v = to[i]] > dis[u] + w[i]) dis[v] = dis[u] + w[i], q.push((node) {v, dis[v]}); } }/* void doit() { rep(i, 1, n) la[i] = pre[i]; } bool check() { int a = n, b = n; while(a != 1 && b != 1) { a = la[a], b = pre[b]; // printf("%d %d!!\n", a, b); if(a != b) return true; } return false; }*/ void solve() { init(); scanf("%d%d%lld%d", &t, &n, &k, &m); rep(i, 1, m) { int x, y, z; scanf("%d%d%d", &x, &y, &z); add(x, y, z); add(y, x, z); } scanf("%d", &d); rep(i, 1, d) { int u, l, r; scanf("%d%d%d", &u, &l, &r); rep(j, l, r) pd[u][j] = 1; } rep(i, 1, t) rep(j, i, t) {// doit(); dij(1, i, j);// res += dis[n]; cost[i][j] = dis[n] >= oo ?dis[n] : dis[n] * (j-i+1); // if(check()) ++cnt; } memset(f, 0x3f3f3f, sizeof(f)); f[0] = 0; rep(i, 1, t) rep(j, 0, i-1) f[i] = min(f[i], f[j]+cost[j+1][i]+k); printf("%lld\n", f[t]-k); }}T;int main() {#ifndef ONLINE_JUDGE freopen("trans.in", "r", stdin); freopen("trans.out", "w", stdout);#endif T.solve(); return 0;}
毕。