首页 > 代码库 > 11.10模拟
11.10模拟
得了92.5分。辣鸡。懒惰的我不想去掉红字了，凑合着看吧。
题解：考试的时候想用搜索做，写min函数的时候定义成了bool型，
，找了半天错误，咋就是返回1.然后还是可爱的小qg提醒，才知道要处理环。
#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#include<cmath>#include<ctime>#define N 10010#define M 100010#define ll long longusing namespace std;int n,m,cnt(0);ll v[N];int num[N][2];ll minn;bool f[N]={0},vis[N];struct node{ int z; int x,y; }a[M];int min(ll x,ll y){ if (x<y) return x; else return y;}ll dfs(int ki){ if (clock()>900) { printf("%d\n",f[1]); fclose(stdin); fclose(stdout); return 0; } if (vis[ki]) return v[ki]; if (!f[ki]) return v[ki]; for (int i=num[ki][0];i<=num[ki][1];i++) { vis[ki]=1; v[ki]=min(v[ki],dfs(a[i].x)+dfs(a[i].y)); vis[ki]=0; } f[ki]=1; return v[ki];}bool cmp(node c,node d){ if (c.z<d.z) return 1; else return 0;}int main(){ freopen("dwarf.in","r",stdin); freopen("dwarf.out","w",stdout); scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%lld",&v[i]); for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i].z,&a[i].x,&a[i].y); sort(a+1,a+m+1,cmp); for (int i=1,k;i<=m;i++) { k=a[i].z; if (!f[k]) f[k]=1,num[a[i-1].z][1]=i-1,num[k][0]=i; } num[a[m].z][1]=m; minn=dfs(1); cout<<minn<<endl; fclose(stdin); fclose(stdout); return 0;}
题解：看了正解之后，哦豁，好神奇，还能用spfa求。由于x，y能合成v，所以x—>v，距离是y；y->v,距离是x。然后跑最短路，这个最短距离就是得到物品i的最小代价。输出到1的最短距离即为解。
#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#include<cmath>#define N 100010#define ll long longusing namespace std;int n,m,Head(0),tail(0),num(0);int vi[N],dis[N],head[N]={0},team[N];bool f[N]={0};struct node{ int v,t,pre;}e[N*2];void add(int to,int from,int dis){ e[++num].v=to; e[num].t=dis; e[num].pre=head[from]; head[from]=num;}void spfa(){ for (int i=1;i<=n;i++) { dis[i]=vi[i]; team[++tail]=i; f[i]=1; } while (Head<=tail) { int k=team[++Head]; f[k]=0; for (int i=head[k];i;i=e[i].pre) { int v=e[i].v; if (dis[v]>dis[k]+dis[e[i].t]) { dis[v]=dis[k]+dis[e[i].t]; if (f[v]==0) { f[v]=1; team[++tail]=v; } } } } }int main(){ freopen("dwarf.in","r",stdin); freopen("dwarf.out","w",stdout); scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&vi[i]); for (int i=1;i<=m;i++) { int v,x,y; scanf("%d%d%d",&v,&x,&y); add(v,x,y); add(v,y,x); } spfa(); printf("%d\n",dis[1]); fclose(stdin); fclose(stdout); return 0;}
11.10模拟
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。