題目描述

給出一張 $n$ 個(gè)點(diǎn) $m$ 條邊的有向圖，邊權(quán)為非負(fù)整數(shù)。求滿足路徑長(zhǎng)度小于等于 $1$ 到 $n$ 最短路 $+k$ 的 $1$ 到 $n$ 的路徑條數(shù)模 $p$ ，如果有無數(shù)條則輸出 $-1$ 。

輸入

第一行包含一個(gè)整數(shù) $T$ , 代表數(shù)據(jù)組數(shù)。

接下來 $T$ 組數(shù)據(jù)，對(duì)于每組數(shù)據(jù)： 第一行包含四個(gè)整數(shù) $N,M,K,P$ ，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開。

接下來 $M$ 行，每行三個(gè)整數(shù) $a_i,b_i,c_i$ ，代表編號(hào)為 $a_i,b_i$ 的點(diǎn)之間有一條權(quán)值為 $c_i$ 的有向邊，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開。

輸出

輸出文件包含 $T$ 行，每行一個(gè)整數(shù)表示答案。

樣例輸入

2
5 7 2 10
1 2 1
2 4 0
4 5 2
2 3 2
3 4 1
3 5 2
1 5 3
2 2 0 10
1 2 0
2 1 0

樣例輸出

3
-1

---

題解

最短路+拓?fù)渑判?#43;dp

首先使用堆優(yōu)化Dijkstra或Spfa（不知道本題是否會(huì)卡）求出1到所有點(diǎn)的最短路。

由于對(duì)于所有邊 $(x,y,z)$ 滿足 $dis[x]+z\ge dis[y]$ ，因此超過最短路的部分不會(huì)減少。

那么我們?cè)O(shè) $f[i][j]$ 表示到達(dá)點(diǎn) $i$ 時(shí)經(jīng)過的路徑總長(zhǎng)度為 $dis[i]+j\ (j \le k)$ 的方案數(shù)。那么這相當(dāng)于一個(gè)新的分層圖，只會(huì)在同層或向上層轉(zhuǎn)移，不會(huì)像下層轉(zhuǎn)移。

這就轉(zhuǎn)化為圖上求路徑條數(shù)。首先初始化 $f[1][0]=0 $ ，跑拓?fù)渑判虻耐瑫r(shí)進(jìn)行轉(zhuǎn)移。

如果一個(gè)點(diǎn)被排到了，那么 $f$ 值即為路徑條數(shù)。

如果一個(gè)點(diǎn)沒有被排到，則說明有環(huán)連接到它，即路徑條數(shù)為 $\infty$。

因此把所有 $f[n][0...k]$ 統(tǒng)計(jì)一下即可。

時(shí)間復(fù)雜度 $O(T(m\log n+mk))$

考場(chǎng)上一眼看出題解，然而卡了兩個(gè)小時(shí)的常數(shù)才勉強(qiáng)卡進(jìn)去...

考場(chǎng)原代碼（去掉了文件操作）：

#include <queue> #include <cctype> #include <cstdio> #include <cstring> #include <algorithm> #define N 100010 #define M 200010 #define R register #define pos(x , y) (x + (y) * n) using namespace std; typedef pair<int , int> pr; priority_queue<pr> q; int head[N] , to[M] , len[M] , next[M] , cnt , dis[N] , vis[N]; int ll[N * 51] , rr[N * 51] , tt[M * 51] , que[N * 51] , ind[N * 51] , f[N * 51]; inline void add(int x , int y , int z) {to[++cnt] = y , len[cnt] = z , next[cnt] = head[x] , head[x] = cnt; } inline char nc() {static char buf[100000] , *p1 , *p2;return p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 100000 , stdin) , p1 == p2) ? EOF : *p1 ++ ; } inline int read() {int ret = 0; char ch = nc();while(!isdigit(ch)) ch = nc();while(isdigit(ch)) ret = ((ret + (ret << 2)) << 1) + (ch ^ '0') , ch = nc();return ret; } int main() {int T = read();while(T -- ){memset(head , 0 , sizeof(head));memset(vis , 0 , sizeof(vis));memset(ind , 0 , sizeof(ind));memset(f , 0 , sizeof(f));cnt = 0;int n = read() , m = read() , k = read() , z , ans = 0 , flag = 1;R int p = read() , i , j , x , y , l = 1 , r = 0;for(i = 1 ; i <= m ; ++i) x = read() , y = read() , z = read() , add(x , y , z);memset(dis , 0x3f , sizeof(dis));dis[1] = 0 , q.push(pr(0 , 1));while(!q.empty()){x = q.top().second , q.pop();if(vis[x]) continue;vis[x] = 1;for(i = head[x] ; i ; i = next[i])if(dis[to[i]] > dis[x] + len[i])dis[to[i]] = dis[x] + len[i] , q.push(pr(-dis[to[i]] , to[i]));}cnt = 0;for(x = 1 ; x <= n ; ++x){for(j = 0 ; j <= k ; ++j){ll[pos(x , j)] = cnt + 1;for(i = head[x] ; i ; i = next[i])if(j + dis[x] + len[i] - dis[to[i]] <= k)++ind[tt[++cnt] = pos(to[i] , j + dis[x] + len[i] - dis[to[i]])];rr[pos(x , j)] = cnt;}}f[1] = 1;for(x = 1 ; x <= pos(n , k) ; ++x)if(!ind[x])que[++r] = x;while(l <= r){x = que[l ++ ];for(i = ll[x] ; i <= rr[x] ; ++i){y = tt[i];f[y] += f[x] , ind[y] -- ;if(f[y] >= p) f[y] -= p;if(!ind[y]) que[++r] = y;}}for(i = 0 ; i <= k ; ++i){if(ind[pos(n , i)]) flag = 0;ans = (ans + f[pos(n , i)]) % p;}if(flag) printf("%d\n" , ans);else puts("-1");}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/GXZlegend/p/7838900.html

總結(jié)

以上是生活随笔為你收集整理的[NOIP2017]逛公园 最短路+拓扑排序+dp的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。