A
模板题,朴素dijkstra,spfa都行,没卡spfa
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10;
int ne[N],h[N],e[N],idx,w[N];
bool st[N];
int dist[N];
int n,m;
int sx,ex;
int spfa(int s)
{
queue<int>q;
dist[s]=0;
st[s]=true;
q.push(s);
while(!q.empty())
{
int ver=q.front();
q.pop();
st[ver]=false;
for(int i=h[ver];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[ver]+w[i])
{
dist[j]=dist[ver]+w[i];
if(!st[j])
{
q.push(j);
st[j]=true;
}
}
}
}
return dist[ex];
}
void add(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int main()
{
while(cin>>n>>m)
{
memset(h,-1,sizeof h);
memset(dist,0x3f,sizeof dist);
memset(st,false,sizeof st);
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c),add(b,a,c);
}
cin>>sx>>ex;
int t=spfa(sx);
if(t==0x3f3f3f3f)cout<<-1<<endl;
else cout<<t<<endl;
}
return 0;
}
B
dfs会tle,用bfs写吧
#include<bits/stdc++.h>
using namespace std;
int dx[8] = { -1,-2,-2,-1,1,2,2,1 };
int dy[8] = { 2,1,-1,-2,2,1,-1,-2 };
bool st[500][500];
int mapp[500][500];
int n, m, x, y;
queue<pair<int, int>>q;
bool check(int a, int b)
{
if (a<1 || a>n || b<1 || b>m || st[a][b])return true;
else return false;
}
int main()
{
memset(mapp, -1, sizeof mapp);
memset(st, false, sizeof st);
cin >> n >> m >> x >> y;
mapp[x][y] = 0,st[x][y]=1;
q.push({x,y});
while (!q.empty())
{
int xx = q.front().first;
int yy = q.front().second;
q.pop();
for (int i = 0; i < 8; i++)
{
int a = xx + dx[i], b = yy + dy[i];
if (check(a, b))continue;
st[a][b] = true;
q.push({ a,b });
mapp[a][b] = mapp[xx][yy] + 1;
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
printf("%d ", mapp[i][j]);
}
printf("\n");
}
return 0;
}
C
并查集+数学
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=1010;
int p[maxn],dist[1010][5];
int flag[maxn];
int n=1010;
void init()
{
for(int i=1;i<=n;i++)
{
p[i]=i;
flag[i]=0;
}
}
int find(int x)
{
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
void add(int x,int y)
{
int fx=find(x);
int fy=find(y);
p[fx]=fy;
}
int main()
{
int m,d,a,b,x,y;
char op[5];
scanf("%d %d",&m,&d);
init();
for(int i=1;i<=m;i++)
{
scanf("%d %d",&dist[i][0],&dist[i][1]);
}
while(~scanf("%s",&op))
{
if(op[0]=='O')
{
scanf("%d",&a);
if(flag[a]==0)
{
flag[a]=1;
for(int i=1;i<=n;i++)
{
x=find(i);
y=find(a);
if(flag[i]&&d*d>=((dist[i][0]-dist[a][0])*(dist[i][0]-dist[a][0])+(dist[i][1]-dist[a][1])*(dist[i][1]-dist[a][1])))
{
if(x!=y)
add(x,y);//baba(i,a);也可以的
}
}
}
}
else
{
scanf("%d %d",&a,&b);
if(find(a)==find(b)) printf("SUCCESS\n");
else printf("FAIL\n");
}
}
return 0;
}