#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,flag1,flag2,flag3,flag4;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(ll i=1;i<=n;i++) {
char c;
cin>>c;
if(i==1) {
if(c=='>') flag1=1;
else flag1=2;
} else if(i==n) {
if(c=='<') flag2=1;
else flag2=2;
}
}
for(ll i=1;i<=m;i++) {
char c;
cin>>c;
if(i==1) {
if(c=='^') flag3=1;
else flag3=2;
} else if(i==m) {
if(c=='v') flag4=1;
else flag4=2;
}
}
if(flag1==1 && flag2==1 && flag3==1 && flag4==1) cout<<"YES";
else if(flag1==2 && flag2==2 && flag3==2 && flag4==2) cout<<"YES";
else cout<<"NO";
return 0;
}
活动打卡代码
AcWing 4801. 强连通图
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,flag1,flag2,flag3,flag4;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(ll i=1;i<=n;i++) {
char c;
cin>>c;
if(i==1) {
if(c=='>') flag1=1;
else flag1=2;
} else if(i==n) {
if(c=='<') flag2=1;
else flag2=2;
}
}
for(ll i=1;i<=m;i++) {
char c;
cin>>c;
if(i==1) {
if(c=='^') flag3=1;
else flag3=2;
} else if(i==m) {
if(c=='v') flag4=1;
else flag4=2;
}
}
if(flag1==1 && flag2==1 && flag3==1 && flag4==1) cout<<"YES";
else if(flag1==2 && flag2==2 && flag3==2 && flag4==2) cout<<"YES";
else cout<<"NO";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll nn=110;
ll n,a[nn],dp[nn][5];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(dp,0x3f,sizeof(dp));
cin>>n;
for(ll i=1;i<=n;i++) cin>>a[i];
dp[0][1]=dp[0][2]=dp[0][3]=0;
for(ll i=1;i<=n;i++) {
if(a[i]==2 || a[i]==3) dp[i][1]=min(dp[i-1][2],dp[i-1][3]);
if(a[i]==1 || a[i]==3) dp[i][2]=min(dp[i-1][1],dp[i-1][3]);
dp[i][3]=min({dp[i-1][1],dp[i-1][2],dp[i-1][3]})+1;
}
cout<<min({dp[n][1],dp[n][2],dp[n][3]});
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x,n;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>x;
n=x;
while(n++) {
ll num=n,i,j,k=0,a[7];
while(num) {
a[++k]=num%10;
num/=10;
}
for(i=1;i<k;i++) {
for(j=i+1;j<=k;j++) {
if(a[i]==a[j]) break;
}
if(j<=k) break;
}
if(i>=k) {
cout<<n;
return 0;
}
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll nn=510;
int n,m,dis[nn];
bool vis[nn];
int g[nn][nn];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(g,0x3f,sizeof(g));
memset(dis,0x3f,sizeof(dis));
cin>>n>>m;
for(ll i=1; i<=m; i++) {
int x,y,z;
cin>>x>>y>>z;
g[x][y]=min(g[x][y],z);
}
dis[1]=0;
for(ll i=1; i<=n; i++) {
ll t=0;
for(ll u=1; u<=n; u++) {
if(vis[u]==0 && dis[t]>dis[u]) t=u;
}
if(t==n) break;
vis[t]=1;
for(ll u=1;u<=n;u++) dis[u]=min(dis[u],dis[t]+g[t][u]);
}
if(dis[n]==0x3f3f3f3f) cout<<-1;
else cout<<dis[n];
return 0;
}
活动打卡代码
AcWing 849. Dijkstra求最短路 I
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll nn=510;
int n,m,dis[nn];
bool vis[nn];
int g[nn][nn];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(g,0x3f,sizeof(g));
memset(dis,0x3f,sizeof(dis));
cin>>n>>m;
for(ll i=1; i<=m; i++) {
int x,y,z;
cin>>x>>y>>z;
g[x][y]=min(g[x][y],z);
}
dis[1]=0;
for(ll i=1; i<=n; i++) {
ll t=0;
for(ll u=1; u<=n; u++) {
if(vis[u]==0 && dis[t]>dis[u]) t=u;
}
if(t==n) break;
vis[t]=1;
for(ll u=1;u<=n;u++) dis[u]=min(dis[u],dis[t]+g[t][u]);
}
if(dis[n]==0x3f3f3f3f) cout<<-1;
else cout<<dis[n];
return 0;
}
静态数组：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll nn=1e5+10;
queue<ll> q;
ll n,m,k,idx,h[nn],vtx[2*nn],nxt[2*nn],in[nn],ans[nn];
void add(ll u,ll v) {
vtx[++idx]=v;
nxt[idx]=h[u];
h[u]=idx;
}
void bfs() {
for(ll i=1; i<=n; i++) {
if(in[i]==0) q.push(i);
}
while(!q.empty()) {
ll u=q.front();
q.pop();
ans[++k]=u;
for(ll i=h[u];i!=-1;i=nxt[i]) {
ll v=vtx[i];
in[v]--;
if(in[v]==0) q.push(v);
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(h,-1,sizeof(h));
cin>>n>>m;
for(ll i=1; i<=m; i++) {
ll a,b;
cin>>a>>b;
add(a,b);
in[b]++;
}
bfs();
if(k==n) {
for(ll i=1;i<=n;i++) cout<<ans[i]<<" ";
} else cout<<-1;
return 0;
}
vector：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll nn=1e5+10;
queue<ll> q;
vector<ll> g[nn];
ll n,m,k,in[nn],ans[nn];
void bfs() {
for(ll i=1; i<=n; i++) {
if(in[i]==0) q.push(i);
}
while(!q.empty()) {
ll u=q.front();
q.pop();
ans[++k]=u;
for(auto v:g[u]) {
in[v]--;
if(in[v]==0) q.push(v);
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(ll i=1; i<=m; i++) {
ll a,b;
cin>>a>>b;
g[a].push_back(b);
in[b]++;
}
bfs();
if(k==n) {
for(ll i=1;i<=n;i++) cout<<ans[i]<<" ";
} else cout<<-1;
return 0;
}
活动打卡代码
AcWing 848. 有向图的拓扑序列
静态数组：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll nn=1e5+10;
queue<ll> q;
ll n,m,k,idx,h[nn],vtx[2*nn],nxt[2*nn],in[nn],ans[nn];
void add(ll u,ll v) {
vtx[++idx]=v;
nxt[idx]=h[u];
h[u]=idx;
}
void bfs() {
for(ll i=1; i<=n; i++) {
if(in[i]==0) q.push(i);
}
while(!q.empty()) {
ll u=q.front();
q.pop();
ans[++k]=u;
for(ll i=h[u];i!=-1;i=nxt[i]) {
ll v=vtx[i];
in[v]--;
if(in[v]==0) q.push(v);
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(h,-1,sizeof(h));
cin>>n>>m;
for(ll i=1; i<=m; i++) {
ll a,b;
cin>>a>>b;
add(a,b);
in[b]++;
}
bfs();
if(k==n) {
for(ll i=1;i<=n;i++) cout<<ans[i]<<" ";
} else cout<<-1;
return 0;
}
vector：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll nn=1e5+10;
queue<ll> q;
vector<ll> g[nn];
ll n,m,k,in[nn],ans[nn];
void bfs() {
for(ll i=1; i<=n; i++) {
if(in[i]==0) q.push(i);
}
while(!q.empty()) {
ll u=q.front();
q.pop();
ans[++k]=u;
for(auto v:g[u]) {
in[v]--;
if(in[v]==0) q.push(v);
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(ll i=1; i<=m; i++) {
ll a,b;
cin>>a>>b;
g[a].push_back(b);
in[b]++;
}
bfs();
if(k==n) {
for(ll i=1;i<=n;i++) cout<<ans[i]<<" ";
} else cout<<-1;
return 0;
}
vector:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll nn=1e5+10;
struct node {
ll u,dis;
};
queue<node> q;
vector<ll> g[nn];
ll n,m;
bool vis[nn];
ll bfs() {
if(1==n) return 0;
vis[1]=1;
q.push({1,0});
while(!q.empty()) {
node tmp=q.front();
q.pop();
for(auto v:g[tmp.u]) {
if(vis[v]==0) {
if(v==n) return tmp.dis+1;
vis[v]=1;
node tmp2={v,tmp.dis+1};
q.push(tmp2);
}
}
}
return -1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(ll i=1;i<=m;i++) {
ll a,b;
cin>>a>>b;
g[a].push_back(b);
}
cout<<bfs();
return 0;
}
静态数组：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll nn=1e5+10;
struct node {
ll u,dis;
};
queue<node> q;
ll n,m,idx,h[nn],vtx[2*nn],nxt[2*nn];
bool vis[nn];
void add(ll u,ll v) {
vtx[++idx]=v;
nxt[idx]=h[u];
h[u]=idx;
}
ll bfs() {
if(1==n) return 0;
vis[1]=1;
q.push({1,0});
while(!q.empty()) {
node tmp=q.front();
q.pop();
for(ll i=h[tmp.u];i!=-1;i=nxt[i]) {
ll v=vtx[i];
if(vis[v]==0) {
if(v==n) return tmp.dis+1;
vis[v]=1;
node tmp2={v,tmp.dis+1};
q.push(tmp2);
}
}
}
return -1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(h,-1,sizeof(h));
cin>>n>>m;
for(ll i=1;i<=m;i++) {
ll a,b;
cin>>a>>b;
add(a,b);
}
cout<<bfs();
return 0;
}
活动打卡代码
AcWing 847. 图中点的层次
vector:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll nn=1e5+10;
struct node {
ll u,dis;
};
queue<node> q;
vector<ll> g[nn];
ll n,m;
bool vis[nn];
ll bfs() {
if(1==n) return 0;
vis[1]=1;
q.push({1,0});
while(!q.empty()) {
node tmp=q.front();
q.pop();
for(auto v:g[tmp.u]) {
if(vis[v]==0) {
if(v==n) return tmp.dis+1;
vis[v]=1;
node tmp2={v,tmp.dis+1};
q.push(tmp2);
}
}
}
return -1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(ll i=1;i<=m;i++) {
ll a,b;
cin>>a>>b;
g[a].push_back(b);
}
cout<<bfs();
return 0;
}
静态数组：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll nn=1e5+10;
struct node {
ll u,dis;
};
queue<node> q;
ll n,m,idx,h[nn],vtx[2*nn],nxt[2*nn];
bool vis[nn];
void add(ll u,ll v) {
vtx[++idx]=v;
nxt[idx]=h[u];
h[u]=idx;
}
ll bfs() {
if(1==n) return 0;
vis[1]=1;
q.push({1,0});
while(!q.empty()) {
node tmp=q.front();
q.pop();
for(ll i=h[tmp.u];i!=-1;i=nxt[i]) {
ll v=vtx[i];
if(vis[v]==0) {
if(v==n) return tmp.dis+1;
vis[v]=1;
node tmp2={v,tmp.dis+1};
q.push(tmp2);
}
}
}
return -1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(h,-1,sizeof(h));
cin>>n>>m;
for(ll i=1;i<=m;i++) {
ll a,b;
cin>>a>>b;
add(a,b);
}
cout<<bfs();
return 0;
}
