Chlience

【题解】[NOIP2017]逛公园 NOIP瞎搞系列
传送门 >ω< UOJ传送门 >ω< LuoguSolution这道题还是有一定难度的首先当然要求出 $1 - n...
扫描右侧二维码阅读全文
19
2018/10

【题解】[NOIP2017]逛公园 NOIP瞎搞系列

传送门 >ω< UOJ
传送门 >ω< Luogu

Solution

这道题还是有一定难度的
首先当然要求出 $1 - n$ 的最短距离

考虑暴力搜索:
找出的路径长度和 $mindis + k$ 对比一下就行

显然这样是会超时的

考虑到如果有多条路径在到达 $x$ 点时已经走过的距离相同,那么他们能从 $x$ 得到的方案数应该也是相同的

那么我们就记录一下 $f[x][y]$ 表示某条路径到达 $x$ 时,若长度为 $y$ ,则有多少种方案

若反向跑出每个点到 $n$ 的距离 $dis$,显然有剪枝 $if(dis[x] + y > mindis + k) f[x][y] = 0;$

那么可以 $mindis + k$ 后面的状态优化掉
复杂度为 $O(T * n * (mindis + k))$
但仍然会超时

观察发现,记录前面 $mindis$ 的状态其实是不需要的,因为最短的路径就是 $mindis$ ,我们只要考虑当前路径比最短路径长了多少就行了

即 $f[x][y]$ 表示:到达 $x$ 节点,在前面的 $1 - x$ 路径上已经浪费了 $y$ 步之后,还有多少种方案到达 $n$

走一条边 $(u , v , w)$ 浪费的价值为 $w - (dis[u] - dis[v])$ ,即比起最短路多走了 $w - (dis[u] - dis[v])$ 的距离

那么转移就很显然了

$$f[u][k] = \sum_{v \in son[x]} f[i][k + w - (dis[u] - dis[v])]$$

最终复杂度为 $O(T * n * k)$

至于判零环比较简单,若搜到同一个节点 $f[x][y]$ 即说明通过零环绕了一圈,直接退出即可

代码

#include <bits/stdc++.h>
using namespace std;

#define L (x << 1)
#define R (x << 1 | 1)
#define mid ((l + r) >> 1)

const int N = 100010;
const int M = 200010;

int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}

int n , m , k , p;
int dis[N];
int u[M] , v[M] , w[M];
struct edge {int t , n , w;}e[M];
int head[N] , tot;

int f[N][60];
bool vis[N][60];
int flag;

void addedge(int u , int v , int w) {
    ++ tot;
    e[tot].t = v;
    e[tot].w = w;
    e[tot].n = head[u];
    head[u] = tot;
}
void clearedge() {
    memset(head , 0 , sizeof(head));
    tot = 0;
}

void cleartag() {
    memset(f , - 1 , sizeof(f));
    memset(vis , 0 , sizeof(vis));
    flag = 0;
}

struct tree {
    int dis[N << 2] , pos[N << 2];
    void update(int x) {
        if(dis[L] > dis[R]) {pos[x] = pos[R]; dis[x] = dis[R];}
        else {pos[x] = pos[L]; dis[x] = dis[L];}
    }
    void build(int x , int l , int r) {
        if(l == r) {pos[x] = l; dis[x] = INT_MAX;}
        else {
            build(L , l , mid);
            build(R , mid + 1 , r);
            update(x);
        }
    }
    void change(int x , int l , int r , int p , int d) {
        if(l == r) dis[x] = d;
        else {
            if(p <= mid) change(L , l , mid , p , d);
            else change(R , mid + 1 , r , p , d);
            update(x);
        }
    }
}t;

void dijistra() {
    for(int i = 1 ; i <= n ; ++ i) dis[i] = INT_MAX;
    dis[n] = 0;
    t.build(1 , 1 , n);
    t.change(1 , 1 , n , n , 0); 
    
    for(int i = 1 ; i < n ; ++ i) {
        int now = t.pos[1];
        for(int j = head[now] ; j ; j = e[j].n) {
            if(dis[e[j].t] > dis[now] + e[j].w) {
                dis[e[j].t] = dis[now] + e[j].w;
                t.change(1 , 1 , n , e[j].t , dis[e[j].t]);
            }
        }
        t.change(1 , 1 , n , now , INT_MAX);
    }
}
void init() {
    n = read(); m = read();
    k = read(); p = read();
    for(int i = 1 ; i <= m ; ++ i) {
        u[i] = read();
        v[i] = read();
        w[i] = read();
    }
}

int dfs(int x , int up) {
    if(vis[x][up] == 1) {flag = 1; return 0;}
    if(f[x][up] != -1) return f[x][up];

    vis[x][up] = 1;
    
    int ans = 0;
    for(int i = head[x] ; i ; i = e[i].n) {
        if(dis[e[i].t] == INT_MAX || up + (e[i].w - dis[x] + dis[e[i].t]) > k) continue;
        
        ans += dfs(e[i].t , up + (e[i].w - dis[x] + dis[e[i].t]));
        if(ans >= p) ans -= p;
        if(flag) return 0;
    }
    
    vis[x][up] = 0;
    if(x == n) ++ ans;
    return f[x][up] = ans;
}

void work() {
    init();
    
    clearedge();
    for(int i = 1 ; i <= m ; ++ i) addedge(v[i] , u[i] , w[i]);
    dijistra();

    clearedge();
    for(int i = 1 ; i <= m ; ++ i) addedge(u[i] , v[i] , w[i]);
    
    cleartag();

    if(dis[1] == INT_MAX) puts("0");
    else {
        int ans = dfs(1 , 0);
        if(!flag) printf("%d\n" , ans);
        else puts("-1");
    }
}
int main() {
    int t = read();
    while(t --) work();
    return 0;
}
Last modification:October 19th, 2018 at 11:14 am

Leave a Comment