「NOIP2017」逛公园

发布于 2018-08-03  291 次阅读


题意描述

给定一张无向图,定义 $ S $ 为 $ 1 $ 到 $ N $ 的最短路,求该无向图 $ 1 $ 到 $ N $ 的路径中长度小于等于 $ S+K $ 的方案。

题目链接

推荐大家去 uoj 多交一些题目,上面有很多 hack 数据。(像我之前认为 dij 就是 spfa+priority_queue)。

解题报告

这一题我们首先一定要跑一遍从 $n$ 到 $1$ 的最短路,记录下 $n$ 到 $i$ 的最短路径长度 $dis_i$

我们考虑动态规划。最长为 $N+k$ 可以理解为你可以多跑长度 $k$。

这样我们写一个 dfs 来搜索,然后无脑记忆化一下。

设 $f[v][i]$ 表示到第 $v$ 个点,走目前的路+之后走最短路到达终点的花费大于最短路不超过 $k$ 的路径条数。

深搜到每一个点的时候如果这一个点是 $n$ 就当前状态记录的答案 $ +1$。枚举这个点指向的点 $next$ 和出边 $w$,转移有 $f[v][i] \to f[next][dis_{next}+w-dis_v]​$ 。

为什么从 $n$ 跑到 $1$ 的原因就是避免掉那些走不到终点的点也加入状态。

然后判断无限多解。只需要一个状态在同一条路径中出现了两次就有无限多种解了。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------\n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 100000 + 5;
const int MAXM = 200000 + 5;

int N,M,K,P;

struct Node{
    struct Edge *firstEdge;
    int dist,num;
    bool used;
}node[MAXN],rnode[MAXN];

struct Edge{
    Node *s,*t;
    int w;
    Edge *next;
}pool[MAXM<<1],*frog = pool;

Edge *New(Node *s,Node *t,int w){
    Edge *ret = ++frog;
    ret->s = s;ret->t = t;ret->w = w;
    ret->next = s->firstEdge;
    return ret;
}

inline void add(int u,int v,int w){
    node[u].firstEdge = New(&node[u],&node[v],w);
    rnode[v].firstEdge = New(&rnode[v],&rnode[u],w);
}

#define P std::pair
#define MP std::make_pair

inline void dij(){
    std::priority_queue,std::greater

>q; FOR(i,1,N){ node[i].num = rnode[i].num = i; rnode[i].dist = INT_MAX; rnode[i].used = false; } q.push(MP(rnode[N].dist=0,&rnode[N])); while(!q.empty()){ Node *v = q.top().second;q.pop(); if(v->used) continue; v->used = true; for(Edge *e = v->firstEdge;e;e = e->next){ if(e->t->dist > v->dist + e->w){ e->t->dist = v->dist + e->w; q.push(MP(e->t->dist,e->t)); } } } } int f[MAXN][100]; int vis[MAXN][100]; int ha; int dfs(Node *v,int k){ if(vis[v->num][k]) return -1; if(f[v->num][k]) return f[v->num][k]; vis[v->num][k] = true; f[v->num][k] = (v->num == N) ? 1 : 0; for(Edge *e = v->firstEdge;e;e = e->next){ int t = rnode[e->t->num].dist+e->w-rnode[v->num].dist; if(t <= k && t >= 0){ int res = dfs(e->t,k-t); if(res == -1) return f[v->num][k] = -1; f[v->num][k] = (f[v->num][k] + res)%ha; } } vis[v->num][k] = false; return f[v->num][k]; } inline void Solve(){ CLR(f,0);CLR(vis,false); frog = pool; scanf("%d%d%d%d",&N,&M,&K,&ha); CLR(node,0);CLR(rnode,0); FOR(i,1,M){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); } dij(); int ans = dfs(&node[1],K); printf("%d\n",ans); } int main(){ int T;scanf("%d",&T); while(T--) Solve(); return 0; }


一个OIer。