题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5+10,M=2*N,S=55;
int n,m,K,P;
int f[N][S],dis[N];
int  e[M], ne[M],w[M],idx;
int h[N],rh[N];
bool st[N],vis[N][S],over[N][S],ep=false;
void add(int q[],int a,int b,int c){
    e[idx]=b,w[idx]=c;ne[idx]=q[a],q[a]=idx++;
}
void init(){
    ep=false;
    idx=0;
    memset(dis,0x3f,sizeof(dis));
    memset(st, 0, sizeof st);
    memset(h, -1, sizeof h);
    memset(rh,-1,sizeof(rh));
    memset(f,-1,sizeof(f));
    memset(over,0,sizeof(over));
    memset(vis,0,sizeof(vis));
}
void inline dijkstra()
{
    dis[n]=0;
    priority_queue<PII,vector<PII>,greater<PII>> q;
    q.push({0,n});
    while(q.size())
    {
        PII t=q.top();
        q.pop();
        if(st[t.second]) continue;
       // cout<<t.second<<"\n";
        st[t.second]=true;
        for(int i=rh[t.second];~i;i=ne[i])
        {
            int j=e[i];
           // cout<<j<<"\n";
            if(dis[t.second]+w[i]<dis[j]){
                dis[j]=dis[t.second]+w[i];
                q.push({dis[j],j});
            }
        }
    }
}
int dfs(int u,int res)
{
    if(res < 0)return 0;
    if(vis[u][res]){over[u][res] = 1;return 0;}
    if(f[u][res] != -1)return f[u][res];
    vis[u][res] = 1;
    int now = u == n;//可能从n出去再回来
    for(int i = h[u]; ~i ;i = ne[i])
    {
        int v = e[i];
        int t = dfs(v,res - ( w[i] - (dis[u] - dis[v]) ));
        if(t == -1)return -1;
        now = (now + t) % P;
    }

    vis[u][res] = 0;
    f[u][res] = now;
    if(f[u][res] > 0 && over[u][res])return -1;//有环且是有效路径才算无解
    return now;
}

int main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--){
        init();
        cin>>n>>m>>K>>P;
        for(int i=1;i<=m;i++){
            int a,b,c;
            cin>>a>>b>>c;
           // cout<<a<<" "<<b<<" "<<c<<"\n";
            add(h,a,b,c);
            add(rh,b,a,c);
        }
        dijkstra();
        //for(int i=1;i<=n;i++) cout<<dis[i]<<endl;
        cout<<dfs(1,K)<<"\n";
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla