题目描述
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