首页 > 代码库 > 2017 计蒜之道 复赛 Windows画图+百度地图导航
2017 计蒜之道 复赛 Windows画图+百度地图导航
因为没有休息好, 打着很异常难受的一场比赛,坚持了一个半小时就撤了。
Windows画图:签到题,没什么说的.
#include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> #include<iostream> #include<queue> #include<map> #include<cmath> #include<set> #include<stack> #define ll long long #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define cls(name,x) memset(name,x,sizeof(name)) using namespace std; const int inf=1<<28; const int maxn=80010; const int maxm=300; const int mod=1e9+7; const double pi=acos(-1.0); int n,m; int mapp[maxm][maxm]; void func(int x1,int y1,int x2,int y2,int c) { if(x1>x2) {swap(x1,x2);swap(y1,y2);} for(int i=0;x1+i<=x2;i++) { if((y2-y1)*(i)%(x2-x1)==0) mapp[x1+i][y1+(y2-y1)*(i)/(x2-x1)]=c; } } int main() { //freopen("in.txt","r",stdin); while(~scanf("%d %d",&n,&m)) { cls(mapp,0); for(int i=1;i<=n;i++) { int x1,y1,x2,y2; scanf("%d %d %d %d",&x1,&y1,&x2,&y2); func(x1,y1,x2,y2,i); } int q; scanf("%d",&q); while(q--) { int a,b; scanf("%d %d",&a,&b); printf("%d\n",mapp[a][b]); } } return 0; }
百度地图导航 官方题解:
把每个城市群抽象成两个点 s‘, s‘‘??。按照如下方式见图:
对于每个城市群里面的城市 s_i??,连边:(s_i, s‘, 0), (s‘‘, s_i, 0);
第一种边正常连边:(u, v, c), (v, u, c);
第二种边连边:(a‘, b‘‘, l), (b‘, a‘‘, l)。
然后跑一遍 s-t 最短路就是答案。
#include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> #include<iostream> #include<queue> #include<map> #include<cmath> #include<set> #include<stack> #define ll long long #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define cls(name,x) memset(name,x,sizeof(name)) using namespace std; const int inf=1<<28; const int maxn=20010; const int maxm=20010; const int mod=1e9+7; const double pi=acos(-1.0); int n,m; struct node { int to,next; ll cost; }edge[maxn*3*2]; int cnt,head[maxn*3]; ll dist[maxn*3]; int vis[maxn*3]; void addedge(int st,int ed,ll cost) { edge[cnt].to=ed; edge[cnt].cost=cost; edge[cnt].next=head[st]; head[st]=cnt++; } void spfa(int s,int t) { for(int i=1;i<=n+m+m;i++) dist[i]=1e18,vis[i]=0; queue<int> Q; Q.push(s); vis[s]=1; dist[s]=0; while(!Q.empty()) { int x=Q.front(); Q.pop(); vis[x]=0; for(int i=head[x];i!=-1;i=edge[i].next) { int to=edge[i].to; if(dist[to]>dist[x]+edge[i].cost) { dist[to]=dist[x]+edge[i].cost; if(!vis[to]) { vis[to]=1; Q.push(to); } } } } if(dist[t]==1e18) printf("-1\n"); else printf("%lld\n",dist[t]); } int main() { //freopen("in.txt","r",stdin); while(~scanf("%d %d",&n,&m)) { cls(head,-1); cnt=0; int k; for(int i=1;i<=m;i++) { scanf("%d",&k); while(k--) { int p; scanf("%d",&p); addedge(p,i+n,0); addedge(i+n+m,p,0); } } scanf("%d",&k); for(int i=1;i<=k;i++) { int a,b; ll c; scanf("%d %d %lld",&a,&b,&c); addedge(a,b,c); addedge(b,a,c); } scanf("%d",&k); for(int i=1;i<=k;i++) { int a,b; ll c; scanf("%d %d %lld",&a,&b,&c); addedge(a+n,b+n+m,c); addedge(b+n,a+n+m,c); } int st,ed; scanf("%d %d",&st,&ed); spfa(st,ed); } return 0; }
2017 计蒜之道 复赛 Windows画图+百度地图导航
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。