首页 > 代码库 > SDUT_人活着系列
SDUT_人活着系列
SDUT2929_人活着系列之芳姐和芳姐的猪
解题报告
求出所有最短路,枚举一个猪圈求出到有猪的猪圈的总路程最短。
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define inf 99999999 using namespace std; struct E { int v,w,next; } edge[5000]; int head[1000],cnt,n,m,k,dis[1000][1000],vis[1000]; int _hash[1000]; void spfa(int s) { queue<int>Q; int i,j; for(i=1; i<=m; i++) { dis[s][i]=inf; vis[i]=0; } dis[s][s]=0; vis[s]=1; Q.push(s); while(!Q.empty()) { int u=Q.front(); Q.pop(); vis[u]=0; for(i=head[u]; i!=-1; i=edge[i].next) { if(dis[s][edge[i].v]>dis[s][u]+edge[i].w) { dis[s][edge[i].v]=dis[s][u]+edge[i].w; if(!vis[edge[i].v]) { vis[edge[i].v]=1; Q.push(edge[i].v); } } } } } void add(int u,int v,int w) { edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } int main() { int i,j,t,u,v,w; while(~scanf("%d%d%d",&n,&m,&k)) { cnt=0; memset(head,-1,sizeof(head)); memset(_hash,0,sizeof(_hash)); memset(edge,0,sizeof(edge)); for(i=1; i<=n; i++) { scanf("%d",&t); _hash[t]++; } for(i=1; i<=k; i++) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } for(i=1; i<=m; i++) { spfa(i); } int minn=inf,sum; for(i=1; i<=m; i++) { sum=0; for(j=1; j<=m; j++) { if(_hash[j]) sum+=dis[i][j]*_hash[j]; } if(minn>sum) { minn=sum; } } printf("%d\n",minn); } return 0; }
SDUT2930_人活着系列之开会
解题报告
求出到‘Z‘岛的所有最短路,再求出最先到达主岛的小岛
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define inf 99999999 using namespace std; struct E { int v,w,next; } edge[50000]; int head[1000],dis[1000],vis[1000],cnt,m,_hash[1000]; void add(int u,int v,int w) { edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } void spfa(int s) { int i,j; for(i='A'; i<='z'; i++) { dis[i]=inf; vis[i]=0; } vis[s]=1; dis[s]=0; queue<int>Q; Q.push(s); while(!Q.empty()) { int u=Q.front(); Q.pop(); vis[u]=0; for(i=head[u]; i!=-1; i=edge[i].next) { if(dis[edge[i].v]>dis[u]+edge[i].w) { dis[edge[i].v]=dis[u]+edge[i].w; if(!vis[edge[i].v]) { vis[edge[i].v]=1; Q.push(edge[i].v); } } } } } int main() { int i,j,w; char a[10],b[10]; while(~scanf("%d",&m)) { memset(head,-1,sizeof(head)); memset(_hash,0,sizeof(_hash)); memset(edge,0,sizeof(edge)); cnt=0; for(i=1; i<=m; i++) { scanf("%s%s%d",a,b,&w); int u=a[0]; int v=b[0]; _hash[u]=1; _hash[v]=1; add(u,v,w); add(v,u,w); } spfa('Z'); int minn=inf,u; for(i='A'; i<'Z'; i++) { if(_hash[i]) { if(minn>dis[i]) { minn=dis[i]; u=i; } } } printf("%c %d\n",u,minn); } }
解题报告
注意是每次拿一块饼来切,所以答案就是k-1
SDUT2932_人活着系列之你的背包
解题报告
简单的素数筛。
SDUT2933_人活着系列之Streetlights
解题报告
裸最小生成树
SDUT2937_人活着系列之寻找最完美的人生
解题报告
可贪心,可最小生成树。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。