Description

策策同學特別喜歡逛公園。公園可以看成一張n個點m條邊構成的有向圖，且沒有自環和重邊。其中1號點是公園的入口，n號點是公園的出口，每條邊有一個非負權值，代表策策經過這條邊所要花的時間。策策每天都會去逛公園，他總是從1號點進去，從n號點出來。策策喜歡新鮮的事物，他不希望有兩天逛公園的路線完全一樣，同時策策還是一個特別熱愛學習的好孩子，他不希望每天在逛公園這件事上花費太多的時間。如果1號點到n號點的最短路長為e，那么策策只會喜歡長度不超過e + k的路線。策策同學想知道總共有多少條滿足條件的路線，你能幫幫他嗎？為避免輸出過大，答案對p取模。如果有無窮多條合法的路線，請輸出?1。

Input

輸入文件名為 park.in 。
第一行包含一個整數 T, 代表數據組數。
接下來T組數據，對于每組數據：
第一行包含四個整數 n,m,k,p，每兩個整數之間用一個空格隔開。
接下來N行，每行三個整數 bi,ci,di ， 代表編號為 bi,ci 的點之間有一條權值為 di 的有向邊，每兩個整數之間用一個空格隔開。

Output

輸出文件包含 T 行，每行一個整數代表答案。

Sample Input

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

Sample Output

3
-1

樣例說明：

對于第一組數據，最短路為 3。
1 – 5, 1 – 2 – 4 – 5, 1 – 2 – 3 – 5 為 3 條合法路徑。

Data Constraint

對于不同的測試點，我們約定各種參數的規模 不會超過如下

對于 100%的數據, 1≤p≤109,1≤bi,ci≤n,0≤di≤1000 。

Solution

• 這題如果直接DP的話，會發現有后效性，則會重復統計答案。

• 但看到 k≤50 ，很小，于是我們考慮拆點。

• 先做一次 Spfa ，設 1 到 i 號點的最短路為 dis[i] 。

• 之后把每個點拆成 k+1 個點，分別對應到這個點時的路徑長 j?dis[i] 的值。

• 由于這個值的范圍只在 [0,k] 之間，

• 那么我們對于開始時的有向邊的兩個點拆點，并進行進行連接。

• 這樣我們就構成了一個拓撲圖，跑一遍拓撲排序即可。

• 當跑完后發現并沒有遍歷所有點，則直接輸出 -1 即可。

• 而且這題還要卡卡常，發現連邊時連接了很多無用點，拖慢了拓撲排序的速度。

• 于是我們考慮倒著做一遍 Spfa （從 n 開始）。

• 當一個點 dis[i]+dis1[i]>dis[n]+k 時，說明這個點就沒用了，不需要從它連邊出去。

• 時間復雜度 O(T?M?K) 。

Code

#include<cstdio> #include<cstring> #include<cctype> using namespace std; const int N=1e5+1,K=51; int n,m,k,p,tot,ans=0; int first[N],next[N<<1],en[N<<1],w[N<<1]; int first1[N*K],next1[N*K<<1],en1[N*K<<1],d[N*K]; int q[N<<6],dis[N],dis1[N],u[N<<1],v[N<<1],t[N<<1],f[N*K]; bool bz[N]; inline int read() {int X=0,w=1; char ch=0;while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}while(isdigit(ch)) X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline void insert(int x,int y,int z) {next[++tot]=first[x];first[x]=tot;en[tot]=y;w[tot]=z; } inline void insert1(int x,int y) {next1[++tot]=first1[x];first1[x]=tot;en1[tot]=y;d[y]++; } inline int get(int x,int y) {return (x-1)*(k+1)+y+1; } int main() {int T=read();while(T--){n=read(),m=read(),k=read(),p=read();memset(first,tot=0,sizeof(first));for(int i=1;i<=m;i++){u[i]=read(),v[i]=read(),t[i]=read();insert(u[i],v[i],t[i]);}memset(dis,60,sizeof(dis));int l=dis[1]=0,r=q[1]=1;while(l<r){int x=q[++l];bz[x]=false;for(int i=first[x];i;i=next[i])if(dis[x]+w[i]<dis[en[i]]){dis[en[i]]=dis[x]+w[i];if(!bz[en[i]]) bz[q[++r]=en[i]]=true;}}memset(first,tot=0,sizeof(first));for(int i=1;i<=m;i++) insert(v[i],u[i],t[i]);memset(dis1,60,sizeof(dis1));l=dis1[q[r=1]=n]=0;while(l<r){int x=q[++l];bz[x]=false;for(int i=first[x];i;i=next[i])if(dis1[x]+w[i]<dis1[en[i]]){dis1[en[i]]=dis1[x]+w[i];if(!bz[en[i]]) bz[q[++r]=en[i]]=true;}}memset(first1,tot=0,sizeof(first1));memset(d,0,sizeof(d));for(int i=1;i<=m;i++){int x=get(u[i],0),y=get(v[i],dis[u[i]]+t[i]-dis[v[i]]);for(int j=dis[u[i]];j+t[i]+dis1[v[i]]<=dis[n]+k;j++,x++,y++) insert1(x,y);}int num=(k+1)*n,sum=0;l=r=ans=0;memset(f,0,sizeof(f));for(int i=1;i<=num;i++)if(!d[i]) q[++r]=i;f[1]=1;while(l<r){int x=q[++l];sum++;for(int i=first1[x];i;i=next1[i]){if(!--d[en1[i]]) q[++r]=en1[i];f[en1[i]]+=f[x];f[en1[i]]=f[en1[i]]>p?f[en1[i]]-p:f[en1[i]];}}if(sum<num) printf("-1\n"); else{for(int i=0;i<=k;i++) ans=(ans+f[get(n,i)])%p;printf("%d\n",ans);}}return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5475. 【NOIP2017提高组正式赛】逛公园的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。