记忆化搜索
跑一次反向的最短路求出
表示的方案数,答案就是
考虑
同样的道理走这条边的话,
⇒
这样怎么判环呢?只要在搜索的时候记录个就了
如果当前的转状态还在搜索的栈中就可以直接返回了
AC code:
#include
using namespace std;
inline void read(int &num)
{
char ch; int flag=1;
while(!isdigit(ch=getchar()))if(ch=='-')flag=-flag;
for(num=ch-'0';isdigit(ch=getchar());num=num*10+ch-'0');
num*=flag;
}
const int MAXN = 100005;
const int MAXM = 200005;
const int MAXK = 55;
int n, m, k, p, f[MAXN][MAXK];
bool instk[MAXN][MAXK];
int fir[MAXN], to[MAXM], nxt[MAXM], wt[MAXM], cnt;
int rfir[MAXN], rto[MAXM], rnxt[MAXM], rwt[MAXM], rcnt;
inline void Add(int u, int v, int w) { to[++cnt] = v; nxt[cnt] = fir[u]; fir[u] = cnt; wt[cnt] = w; }
inline void rAdd(int u, int v, int w) { rto[++rcnt] = v; rnxt[rcnt] = rfir[u]; rfir[u] = rcnt; rwt[rcnt] = w; }
int dis[MAXN];
bool inq[MAXN];
queueQ;
void spfa(int T)
{
memset(dis, 0x7f, sizeof dis);
dis[T] = 0; inq[T] = 1; Q.push(T);
while(!Q.empty())
{
int u = Q.front(); inq[u] = 0; Q.pop();
for(int i = rfir[u]; i; i = rnxt[i])
if(dis[rto[i]] > dis[u] + rwt[i])
{
dis[rto[i]] = dis[u] + rwt[i];
if(!inq[rto[i]])
inq[rto[i]] = 1, Q.push(rto[i]);
}
}
}
int dfs(int u, int now)
{
if(instk[u][now]) return -1;
if(f[u][now]) return f[u][now];
instk[u][now] = 1;
if(u == n) f[u][now] = 1;
for(int i = fir[u], tmp; i; i = nxt[i])
if(dis[to[i]]-dis[u]+wt[i]
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.e1idc.net