解题思路:
暴力搜索加最优化剪枝
注意事项:不想填(滑稽)
参考代码:
#include<cstdio> #include<cstring> #include<iostream> using namespace std; int mid[10]; int n,m,q; int E[10],F[10]; int x,y,z,d; int lin[105],cnt; struct str { int next,y,z,d; }e[10005]; void insertt() { e[++cnt].y=y; e[cnt].next=lin[x]; lin[x]=cnt; e[cnt].z=z; e[cnt].d=d; } int vis[105]; int ans,temp; void work(int x) { if(x==n-1) { ans=ans>temp?temp:ans; return ; } if(temp>=ans)return ; for(int i=lin[x];i;i=e[i].next) { if(!vis[e[i].y]) { vis[e[i].y]=1; temp+=e[i].d; int tt=++mid[e[i].z]; if(tt==2)temp+=E[e[i].z]; else if(tt>2)temp+=F[e[i].z]; work(e[i].y); if(tt==2)temp-=E[e[i].z]; else if(tt>2)temp-=F[e[i].z]; --mid[e[i].z]; vis[e[i].y]=0; temp-=e[i].d; } } } int main() { while(scanf("%d%d%d",&n,&m,&q)!=EOF) { cnt=0; memset(e,0,sizeof(e)); memset(lin,0,sizeof(lin)); memset(mid,0,sizeof(mid)); memset(vis,0,sizeof(vis)); for(int i=0;i<m;i++) scanf("%d",&E[i]); for(int i=0;i<m;i++) scanf("%d",&F[i]); for(int i=0;i<q;i++) { scanf("%d%d%d%d",&x,&y,&z,&d); insertt(); } ans=2000000000; temp=0; work(0); printf("%d\n",ans); } return 0; }
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:603 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:746 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:1030 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:599 |
WU-拆分位数 (C++代码)浏览:779 |
C语言程序设计教程(第三版)课后习题6.2 (C语言代码)浏览:703 |
模拟计算器 (C++代码)浏览:803 |
上车人数 (C语言代码)浏览:710 |
字符删除 (C语言代码)浏览:716 |
C二级辅导-统计字符 (C语言描述——用函数求解)浏览:1178 |