题目大意

给你一张无向图,某些时刻某些点以及其所连的边被删除,请你求出一组最短路,使得总长度+改动费用最小。

解题思路

一直在想用最短路上的dp。然后发现要状压,然而我并不会状压,后来又发现转移代价已经可以上天了。
然后终于明白,这实际上是一种类似与石子合并的dp。
你可以枚举在哪一天换方案,然后接下来那些天走同一种方案,记录最小代价即可。
costi 表示从第i天到第j天走同一方案的代价,若行不通则值为INF。
dpi] 表示前i天最小代价,转移方程:dp[i] = dp[j]+cost[j+1*天数 (0<j<i)
复杂度分析:预处理出cost数组,需要枚举O(n^2)的状态,对于每个状态跑一遍最短路O(elogm),e为边数,m为点数。
然后O(n^2)的dp,总复杂度:O(n^2*elogm + n^2).

代码

#include <bits/stdc++.h>

#define INF 1000000000

using namespace std;

typedef long long LL;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int N, M, K, D, e_num;
LL dp[105];
struct Bad{
    int P;
    int begin;
    int end;
}bad[101];
LL cost[101][101]; //cost[i][j]表示从第i天到第j天走相同航线的最短路径长度
bool can[21]; //表示某港口是否可行
vector<int> edge[21];
vector<int> len[21];

void DEBUG();

void Input()
{
    N=read(); M=read(); K=read(); e_num=read();
    for(int i=1; i<=e_num; i++)
    {
        int u=read(), v=read(), l=read();
        edge[u].push_back(v);
        len[u].push_back(l);
        edge[v].push_back(u);
        len[v].push_back(l);
    }
    D = read();
    for(int i=1; i<=D; i++)
    {
        bad[i].P = read();
        bad[i].begin = read();
        bad[i].end = read();
    }
}

struct HeapNode{
    int dis, node;
    bool operator < (const HeapNode& rhs) const{
        return dis > rhs.dis;
    }
};

int Dijkstra()
{
    int dis[21];
    bool done[21];
    for(int i=1; i<=M; i++)
    {
        dis[i] = INF;
        done[i] = false;
    }
    dis[1] = 0;
    priority_queue<HeapNode> Q;
    Q.push((HeapNode){0,1});
    while( !Q.empty() )
    {
        HeapNode t = Q.top(); Q.pop();
        int now = t.node;
        if(done[now]) continue;
        done[now] = true;
        if(done[M]) break;
        int sz = edge[now].size();
        for(int i=0; i<sz; i++)
        {
            int v = edge[now][i];
            if(can[v] && !done[v] && dis[now]+len[now][i] < dis[v])
            {
                dis[v] = dis[now]+len[now][i];
                Q.push((HeapNode){dis[v],v});
            }
        }
    }
    return dis[M];
}

void Calculate_cost()
{
    for(int ii=1; ii<=N; ii++)
        for(int jj=ii; jj<=N; jj++)
        {
            for(int i=1; i<=M; i++) can[i] = true;
            for(int i=1; i<=D; i++)
            {
                if(ii<=bad[i].begin && bad[i].begin<=jj) can[bad[i].P] = false;
                if(ii<=bad[i].end && bad[i].end<=jj) can[bad[i].P] = false;
                if(ii<=bad[i].begin && bad[i].end<=jj) can[bad[i].P] = false;
                if(bad[i].begin<=ii && jj<=bad[i].end) can[bad[i].P] = false;
            }
            cost[ii][jj] = Dijkstra();
        }
}

void Solve()
{
    for(int i=1; i<=N; i++) dp[i] = INF;
    dp[0] = 0;
    dp[1] = cost[1][1];
    for(int i=2; i<=N; i++)
    {
        dp[i] = cost[1][i]*i;
        for(int j=0; j<i; j++)
        {
            LL cost_t = dp[j]+(LL)(cost[j+1][i]*(i-j))+K;
            if(cost_t < dp[i]) dp[i] = cost_t;
        }
    }
    cout<<dp[N]<<endl;
}

int main()
{
    freopen("input.in","r",stdin);
    freopen("outiput.out","w",stdout);
    Input();
    Calculate_cost();
    Solve();
    fclose(stdin); fclose(stdout);
    return 0;
}