/****************************************\
* Author : ztx
* Title  : [ZJOI2006]物流运输trans
* ALG    : 最短路 dp
* CMT    : dp(i) = min(length(1,i)*i , dp(j)+length(j+1,i)*(i-j)+k) ;
*          { 1 <= j < i }
*          length(i,j)表示从第 i 天到第 j 天走同一条道路的最短路径长度
*          特别注意，一个点有可能有多个时间段不能通过 = =
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [ZJOI2006]物流运输trans
* ALG    : 最短路 dp
* CMT    : dp(i) = min(length(1,i)*i , dp(j)+length(j+1,i)*(i-j)+k) ;
*          { 1 <= j < i }
*          length(i,j)表示从第 i 天到第 j 天走同一条道路的最短路径长度
*          特别注意，一个点有可能有多个时间段不能通过 = =
* Time   :
\****************************************/

#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 ;
}

• 相关文章
• 全局相关文章