洛谷P3953 逛公园(dp 拓扑排序)

题意

题目链接

Sol

去年考NOIP的时候我好像连最短路计数都不会啊qwq。。

首先不难想到一个思路,\(f[i][j]\)表示到第\(i\)个节点,与最短路之差长度为\(j\)的路径的方案数

首先把每个节点的最短路求出来

转移的时候按拓扑序(也就是按距离从小到大排序)转移一下

然而有\(0\)边的时候会挂掉,原因是会有dis相同的时候,这时候单按dis排序会无法判断转移方向

一种方案是直接把所有\(0\)边加入到新图中,拓扑排序一遍。得到第二关键字

同时判断一下\(0\)环

#include<bits/stdc++.h>
#define Pair pair<int, int>
#define MP make_pair
#define fi first
#define se second 
using namespace std;
const int MAXN = 100001, INF = 1e9 + 7;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int T, N, M, K, mod, f[MAXN][51], dis1[MAXN], disn[MAXN], vis[MAXN], inder[MAXN], id[MAXN];
vector<Pair> v[MAXN], rv[MAXN];
vector<pair<pair<int, int>, int> > P;
vector<int> E[MAXN];
void init() {
    memset(f, 0, sizeof(f));
    memset(inder, 0, sizeof(inder));
    P.clear();
    f[1][0] = 1;
    N = read(); M = read(); K = read(); mod = read();
    for(int i = 1; i <= N; i++) v[i].clear(), E[i].clear();
    for(int i = 1; i <= M; i++) {
        int x = read(), y = read(), z = read();
        v[x].push_back(MP(y, z)); rv[y].push_back(MP(x, z));
        if(!z) E[x].push_back(y), inder[y]++;
    }
}
void add(int &x, int y) {
    if(x + y < 0) x = (x + y + mod);
    else x = (x + y >= mod ? x + y - mod : x + y);
}
int Topsort() {
    int cnt = 0; queue<int> q;
    for(int i = 1; i <= N; i++) if(!inder[i]) id[i] = ++cnt, q.push(i);
    while(!q.empty()) {
        int p = q.front(); q.pop();
        for(int i = 0, to; i < E[p].size(); i++) 
            if(!(--inder[to = E[p][i]])) q.push(to), id[to] = ++cnt;
    }
    for(int i = 1; i <= N; i++) if(inder[i] && (dis1[i] + disn[i] <= dis1[N] + K)) return -1;
    return 0;
}
void Dij(int bg, int *dis) {
    priority_queue<Pair> q; q.push(MP(0, bg)); 
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= N; i++) dis[i] = INF + 1; dis[bg] = 0;
    while(!q.empty()) {
        if(vis[q.top().se]) {q.pop(); continue;}
        int p = q.top().se; q.pop(); vis[p] = 1;
        if(bg == 1) {
            for(int i = 0, to; i < v[p].size(); i++) 
                if(dis[to = v[p][i].fi] > dis[p] + v[p][i].se) 
                    dis[to] = dis[p] + v[p][i].se, q.push(MP(-dis[to], to));            
        } else {
            for(int i = 0, to; i < rv[p].size(); i++) 
                if(dis[to = rv[p][i].fi] > dis[p] + rv[p][i].se) 
                    dis[to] = dis[p] + rv[p][i].se, q.push(MP(-dis[to], to));           
        }
    }   
}
int solve() {
    Dij(1, dis1);
    Dij(N, disn);
    if(Topsort() == -1) return -1;
    for(int i = 1; i <= N; i++) P.push_back(MP(MP(dis1[i], id[i]), i));
    sort(P.begin(), P.end());
    f[1][0] = 1;
    for(int j = 0; j <= K; j++) {
        for(int i = 0; i < N; i++) {
            int x = P[i].se;
            for(int k = 0; k < v[x].size(); k++) {
                int to = v[x][k].fi, w = v[x][k].se, ps = dis1[x] + j + w - dis1[to];
                if(ps <= K) add(f[to][ps], f[x][j]);
            }
        }
    }
    int ans = 0;
    for(int i = 0; i <= K; i++) add(ans, f[N][i]);
    return ans;
}
int main() {
    T = read(); 
    while(T--) {
        init();
        printf("%d\n", solve());            
    }
    return 0;
}
/*
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Web行业观察

0.30000000000000004

0.30000000000000004问题是计算机科学领域的经典BUG, 由比尔盖茨那一代人标准化的浮点数表示法造福了一代人也祸害了一代人, 由...

63330
来自专栏数据结构与算法

洛谷P1852 奇怪的字符串

题目描述 输入两个01串,输出它们的最长公共子序列的长度 输入输出格式 输入格式: 一行,两个01串 输出格式: 最长公共子序列的长度 输入输出样例 输入样例#...

33390
来自专栏小樱的经验随笔

Codeforces 791B Bear and Friendship Condition(DFS,有向图)

B. Bear and Friendship Condition time limit per test:1 second memory limit per t...

37390
来自专栏阿凯的Excel

八种方式实现多条件匹配

之前在Excel内部的分享交流群和别的讲师探讨了多条件匹配有哪些实现方式。 围观的市民刘先生表示:我活了二十多年,看见斗图的比较多,这么无聊斗Excel使用技巧...

48540
来自专栏窗户

Scheme来实现八皇后问题(2)

  上一章讲了用1~n的排序来表示n皇后的解,然后通过枚举1~n所有的排列、判定谓词过滤所有排列得到最终的所有解。

15830
来自专栏数据结构与算法

[vijos]lxhgww的奇思妙想(长链剖分)

首先我们维护出每一个重链头向上$len[i]$个节点是什么,沿着重链走向下$len[i]$个节点是什么

13650
来自专栏数据结构与算法

SPOJ COT2 - Count on a tree II(树上莫队)

31430
来自专栏Java爬坑系列

【Java入门提高篇】Day22 Java容器类详解(五)HashMap源码分析(上)

准备了很长时间,终于理清了思路,鼓起勇气,开始介绍本篇的主角——HashMap。说实话,这家伙能说的内容太多了,要是像前面ArrayList那样翻译一下源码,稍...

26250
来自专栏令仔很忙

新手学HighCharts(二)----对比柱状图的动态加载

上一篇文章 新手学HighCharts(一)—-基本使用 中介绍了highCharts的基本使用,今天给大家介绍对比柱状图的使用,贴张图先:

11010
来自专栏云霄雨霁

关系代数

21600

扫码关注云+社区

领取腾讯云代金券