[bzoj] 1003: [ZJOI2006]物流运输trans

发表于   |   分类于   |  

题意

　　给定一有$m$个点的无向图$G$和一个时间$n$, 图中一些点在一些时间段是不能通过的, 你需要在每一天选择$1$至$m$一条路径$P$, 但是如果这条路径与前一天的$P$不同,则需要花费代价$K$.
　　设第$i$天路径$P$长度为$length_i$, 改变路径次数为$c$
最小化

$$c\cdot K+\sum_{i=1}^{n}{length_i}$$

传送门

分析

　　设$len(i,j)$表示从第$i$天到第$j$天走相同的$P$时最短路径长度, $dp(i)$表示前$i$天的最小的$c\cdot K+\sum_{j=1}^{i}{length_j}$

$$ dp(i)=min \lbrace len(1,i)\cdot i,dp(j)+len(j+1,i)\cdotp(i-j)+K | 1\leq j<i \rbrace $$

这道题还需要注意的是一个点有可能有多个时间段不能通过

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

#include <cstdio>

int CH , NEG ;

template<typename T>
inline void read(T& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

typedef long long ll ;

#include <cstring>

#define  maxn  105LL
#define  maxm  25LL
#define  maxd  10010LL
#define  info  0x7f7f7f7f7f7f7f7fLL
/* maxd 坑死人 = = */

int n , m , u , v ;
ll K ;
ll f[maxn] = {0} ;
ll length[maxn][maxn] = {0} ;

ll map[maxm][maxm] = {0} ;
ll dis[maxm] = {0} ;
bool inq[maxm] = {0} ;
int cont_time[maxd][3] = {0} ;
bool cont[maxm] = {0} ;

#define  sizeque  100LL
int q[sizeque] , head , tail ;
inline int F(int x) { return ((x%sizeque)+sizeque)%sizeque ; }
inline void clear() { head = 0 , tail = -1 ; }
inline int front() { return q[F(head)] ; }
inline int back() { return q[F(tail)] ; }
inline void push_front(int x) { q[F(--head)] = x ; }
inline void push_back(int x) { q[F(++tail)] = x ; }
inline void pop_front() { head ++ ;}
inline void pop_back() { tail -- ; }
inline bool empty() { return head > tail ; }

void SPFA(int start , int end) {
    memset(cont , 0 , sizeof cont) ;
    memset(dis , 0x7f , sizeof dis) ; clear() ;
    for (u = 1 ; u <= cont_time[0][0] ; u ++ ) {
        if (cont_time[u][1]>end || cont_time[u][2]<start) continue ;
        else cont[cont_time[u][0]] = true ;
    }
    push_back(1) ; inq[1] = true ; dis[1] = 0 ;
    while (!empty()) {
        u = front() , pop_front() ; inq[u] = false ;
        for (v = 1 ; v <= m ; v ++ ) {
            if (map[u][v]==info || cont[v]) continue ;
            if (dis[v] > dis[u]+map[u][v]) {
                dis[v] = dis[u]+map[u][v] ;
                if (!inq[v]) {
                    inq[v] = true ;
                    if (!empty() && dis[v]<dis[front()]) push_front(v) ;
                    else push_back(v) ;
                }
            }
        }
    }
    if (dis[m] == info) length[start][end] = -1 ;
    else length[start][end] = dis[m] ;
}

int i , j ;
ll tmp ;
int main() {
//  #define READ
    #ifdef  READ
        freopen(".in" ,"r",stdin ) ;
        freopen(".out","w",stdout) ;
    #endif
    read(n) , read(m) , read(K) , read(i) ;
    memset(map , 0x7f , sizeof map) ;
    while (i -- ) {
        read(u) , read(v) , read(tmp) ;
        if (map[u][v] > tmp) { map[u][v] = map[v][u] = tmp ; }
    }
    read(cont_time[0][0]) ;
    for (i = 1 ; i <= cont_time[0][0] ; i ++ ) {
        read(cont_time[i][0]) , read(cont_time[i][1]) , read(cont_time[i][2]) ;
    }
    for (i = 1 ; i <= n ; i ++ )
        for (j = i ; j <= n ; j ++ )
            SPFA(i , j) ;
    memset(f , 0x7f , sizeof f) ;
    f[0] = -K ;
    for (i = 1 ; i <= n ; i ++ ) {
        for (j = 0 ; j < i ; j ++ ) {
            if (f[j]==info || length[j+1][i]<0) continue ;
            tmp = f[j]+(ll)K+(ll)length[j+1][i]*(ll)(i-j) ;
            if (tmp < f[i]) f[i] = tmp ;
        }
    }
    printf("%lld\n", f[n] ) ;
    #ifdef  READ
        fclose(stdin) ; fclose(stdout) ;
    #else
        getchar() ; getchar() ;
    #endif
    return 0 ;
}

热评文章