1 条题解
-
1
#include <cstdio> #include <queue> #include <vector> #include <cstring> using namespace std; int t,d[100001],f[100001][51],n,m,k,p; bool working[100001][51]; struct node { int to,len; }; vector<node>head[100001]; vector<node>h[100001]; //这里用两个vector来存图,初始化的时候非常方便 //,强烈建议使用,不容易出错 int dp(int root, int l){ //这才是这道题的奥妙所在 //root表示到哪个点了,l表当前的k还有多少剩余 int ans=0; //反向跑是因为可以减少跑死胡同的情况增加效率, //一些不能到达n的路径就可以不用跑了,可以自行画图理解 if (l<0||l> k) return 0;//这种情况说明答案不合法 if (working[root][l]) { //working数组是为了判断‘0’环的情况, //当其已经为1时代表它已经跑过了,就可以跳出来了 working[root][l]=false; return -1; } if(f[root][l]!=-1) //f有值了代表求出答案了 return f[root][l]; working[root][l]=true; for (int i=0;i<h[root].size();i++) {//跑反图 node e= h[root][i]; int val=dp(e.to,d[root]+l-d[e.to]-e.len); //这个表达式,表示用尝试当前这条边替换其中最短路径里的一条边 //来求一个合法的解 if (val==-1) { working[root][l]=false; return -1; } ans=(ans+val)%p; } working[root][l] = false; if (root==1&&l==0) ans++; //跑到这里是证明这是一个解ans就+1 f[root][l]=ans;//记录答案 return ans; } int work(){ scanf("%d%d%d%d", &n, &m, &k, &p); for (int i=1;i<=n;i++) {//看,初始化只要几行就好了 head[i].clear(); h[i].clear(); } int a, b, c; for (int i=1;i<= m;i++) {//存图 scanf("%d%d%d",&a,&b,&c); node e; e.to=b; e.len=c; head[a].push_back(e); e.to=a; //反图 h[b].push_back(e); } memset(d,0x3f,sizeof(d)); //spfa memset(f,-1,sizeof(f)); //记得初始化,否则会wa声一片 queue<int>q; q.push(1); d[1]=0; while (!q.empty()) { int x=q.front(); q.pop(); for (int i=0;i<head[x].size();i++) { if (d[head[x][i].to]>d[x]+head[x][i].len) { d[head[x][i].to]=d[x]+head[x][i].len; q.push(head[x][i].to); } } } int ans=0; for (int i=0;i<=k;i++) { //dp 枚举k:0-k, int val=dp(n,i); //求和后就是答案 if (val==-1) return -1; ans=(ans+val)%p; } return ans; } int main(){//简单的主函数 scanf("%d", &t); while(t--) printf("%d\n", work()); return 0; }
- 1
信息
- ID
- 73
- 时间
- 3000ms
- 内存
- 512MiB
- 难度
- 9
- 标签
- 递交数
- 10
- 已通过
- 5
- 上传者