NO IMAGE

題目地址

分析

  • 設dis1[u]dis1[u]表示1→u1 \to u的最短路長度,disn[u]disn[u]表示u→nu \to n的最短路長度

【30pts】拓撲排序 DP

  • 這裡針對的是K=0K = 0的情況,問題轉化為求圖中的最短路徑數
  • 我們先將最短路圖建出來(對於每條邊u→vu \to v,滿足dis1[u] lenu→v=dis1[v]dis1[u] len_{u \to v} = dis1[v]),因為沒有00邊所以就是個有向無環圖,直接按照拓撲序計算DPDP即可

【100pts】記憶化搜尋 DP Tarjan

  • 首先應該能很容易想到這還是個DPDP
  • 然後考慮怎樣定義狀態:
    • 考場上我想得最為簡單暴力,設g[u][k]g[u][k]表示到達點uu,長度為kk的路徑數,顯然g[u][k]=∑g[v][k−lenu→v]g[u][k] = \sum g[v][k – len_{u \to v}],但空間時間都要爆炸,於是粗略算了空間後聽天由命……
    • 但其實能注意到KK的範圍相當小,於是我們設f[u][k]f[u][k]表示到達點uu,長度為dis1[u] kdis1[u] k的路徑數,則轉移為f[u][k]=∑f[v][k−(dis1[u] lenu→v−dis1[v])]f[u][k] = \sum f[v][k – (dis1[u] len_{u \to v} – dis1[v])]
  • 考慮到邊權可能為00,轉移的順序會影響最後的結果,因此我們用記憶化搜尋代替直接DPDP
  • 那麼現在只剩下一個問題:如何判無解
    • 顯然無解的情況就是在滿足條件的路徑上出現00環
    • 如何判斷一個點uu是否在滿足條件的路徑上?顯然我們可以知道這個點滿足dis1[u] disn[u]≤dis1[n] Kdis1[u] disn[u] \le dis1[n] K
    • 我們把所有長度為00的邊建成一個新圖,然後用TarjanTarjan找出所有點數大於11的強連通分量(也就是00環),逐個檢查上面的點即可
  • 時間複雜度O(MK)O(MK)

程式碼

  • 發覺常數巨大,果然蒟蒻
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
inline int get()
{
char ch; int res = 0; bool Flag = false;
while (!isdigit(ch = getchar()));
(ch == '-' ? Flag = true : res = ch ^ 48);
while (isdigit(ch = getchar()))
res = res * 10   ch - 48;
return Flag ? -res : res;
}
const int Maxn = 0x3f3f3f3f;
const int N = 1e5   5, M = N << 1;
int D1[N], Dn[N], h[M], f[N][55], a[N];
int Tm, n, m, K, P, Ans, top, tis; 
int dfn[N], low[N], stk[N]; 
bool vis[N], inv[N], Flag;
struct Edge
{
int to, cst; Edge *nxt;
};
Edge p[M], *T = p, *lst[N];
Edge q[M], *Q = q, *rst[N];
inline void LinkEdge(int x, int y, int z)
{
(  T)->nxt = lst[x]; lst[x] = T; 
T->to = y; T->cst = z;
}
inline void RinkEdge(int x, int y, int z)
{
(  Q)->nxt = rst[x]; rst[x] = Q; 
Q->to = y; Q->cst = z;
}
inline void Spfa(int src, int *dis)
{
for (int i = 1; i <= n;   i) dis[i] = Maxn;
int t = 0, w = 1, x, y; dis[h[1] = src] = 0; 
while (t != w)
{
t; if (t == M) t = 0;
vis[x = h[t]] = false;
for (Edge *e = src == 1 ? lst[x] : rst[x]; e; e = e->nxt)
if (dis[y = e->to] > dis[x]   e->cst)
{
dis[y] = dis[x]   e->cst;
if (!vis[y]) 
{
w; if (w == M) w = 0;
vis[h[w] = y] = true;
}
}
}
}
inline void Add(int &x, int y)
{
x  = y; if (x >= P) x -= P; 
}
inline int Dfs(int x, int d)
{
if (f[x][d] != -1) return f[x][d];
if (x == n && !d) return f[x][d] = 1;
f[x][d] = 0;
for (Edge *e = lst[x]; e; e = e->nxt)
{
int tmp = d - e->cst;
if (tmp >= 0 && tmp <= K)
Add(f[x][d], Dfs(e->to, tmp));
}
return f[x][d];
}
inline void CkMin(int &x, int y)
{
if (x > y) x = y;
}
inline void Tarjan(int x)
{
if (Flag) return ;
dfn[x] = low[x] =   tis; int y;
inv[x] = true; stk[  top] = x;
for (Edge *e = rst[x]; e; e = e->nxt)
{
if (e->cst) continue;
if (!dfn[y = e->to]) 
Tarjan(y), CkMin(low[x], low[y]);
else if (inv[y])
CkMin(low[x], dfn[y]);
}
if (dfn[x] == low[x])
{
inv[x] = false; bool num = false;
while (y = stk[top--], y != x)
inv[y] = false, num = true;
if (D1[x]   Dn[x] <= D1[n]   K && num) Flag = true;
} 
}
int main()
{
//  freopen("park.in", "r", stdin);
//  freopen("park.out", "w", stdout);
Tm = get();
while (Tm--)
{
memset(lst, 0, sizeof(lst)); T = p;
memset(rst, 0, sizeof(rst)); Q = q;
int x, y, z;
n = get(); m = get(); K = get(); P = get();
while (m--)
{
x = get(); y = get(); z = get();
LinkEdge(x, y, z);
RinkEdge(y, x, z);
}
Spfa(1, D1); Spfa(n, Dn);
memset(dfn, 0, sizeof(dfn));
memset(inv, false, sizeof(inv)); Flag = false;
for (int i = 1; i <= n;   i)
if (!dfn[i]) Tarjan(i);
if (Flag) 
{
puts("-1");
continue;
}
for (int i = 1; i <= n;   i)
for (Edge *e = lst[i]; e; e = e->nxt)
e->cst  = D1[i] - D1[e->to];
for (int k = 0; k <= K;   k)
for (int i = 1; i <= n;   i)
f[i][k] = -1;
Ans = 0;
for (int k = 0; k <= K;   k)
Add(Ans, Dfs(1, k));
printf("%d\n", Ans);
}
//  fclose(stdin); fclose(stdout);
return 0;
}