LYDSY 1003

题目大意

暂无

题目解法

暂无

RTFC

#include <cstdio>
#include <cstring>
inline int min(int a, int b) { return a < b ? a : b; }
int next[410], to[410], len[410], G[21], e_idx;
int que[100001], head, tail;
bool inque[21], isbad[21], cant[21][101];
int cost[110][110], f[101];
inline void addEdge(int f, int t, int l)
{
    e_idx++;
    to[e_idx] = t;
    len[e_idx] = l;
    next[e_idx] = G[f];
    G[f] = e_idx;
}
void spfa(int s)
{
    memset(inque, 0, sizeof(inque));
    memset(f, 0x3f, sizeof(f));
    head = tail = 0;
    f[s] = 0;
    que[tail++] = s;
    inque[s] = true;
    while (head < tail)
    {
        int x = que[head++];
        inque[x] = false;
        for (int i = G[x]; i; i = next[i])
            if (!isbad[to[i]])
                if (f[to[i]] > f[x] + len[i])
                {
                    f[to[i]] = f[x] + len[i];
                    if (!inque[to[i]]) inque[que[tail++] = to[i]] = true;
                }
    }
}
int main()
{
    int n, m, k, e, d;
    scanf("%d%d%d%d", &n, &m, &k, &e);
    for (int i = 0, x, y, z; i < e; i++)
    {
        scanf("%d%d%d", &x, &y, &z);
        addEdge(x, y, z);
        addEdge(y, x, z);
    }
    scanf("%d", &d);
    for (int i = 0, x, y, z; i < d; i++)
    {
        scanf("%d%d%d", &x, &y, &z);
        for (int j = y; j <= z; j++)
            cant[x][j] = true;
    }
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
        {
            memset(isbad, 0, sizeof(isbad));
            for (int x = 2; x < m; x++)
                for (int y = i; y <= j; y++)
                    if (cant[x][y])
                    {
                        isbad[x] = true;
                        break;
                    }
            spfa(1);
            cost[i][j] = f[m] * (f[m] > 0x3f3f3f3f >> 1 ? 1 : j - i + 1);
        }
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++)
            f[i] = min(f[i], f[j] + cost[j + 1][i] + k);
    printf("%d", f[n] - k);
    return 0;
}