SPFA模板
1 #define R 400002 2 #include<iostream> 3 #include<vector> 4 #include<queue> 5 using namespace std; 6 int n,m; 7 struct node 8 { 9 int to,w; 10 }; 11 vector<node>adj[R]; 12 int dis[R],z,w,ans=2e9; 13 bool vin[R]; 14 queue<int>qu; 15 void spfa(int s) 16 { 17 int x,y,z; 18 for(int i=1;i<=n;i++) dis[i]=2e9; 19 dis[s]=0; 20 qu.push(s); 21 vin[s]=1; 22 while(qu.size()>0) 23 { 24 x=qu.front(); 25 qu.pop(); 26 vin[x]=0; 27 for(int k=0;k<adj[x].size();k++) 28 { 29 int y=adj[x][k].to; 30 if(dis[y]>dis[x]+adj[x][k].w) 31 { 32 dis[y]=dis[x]+adj[x][k].w; 33 if(!vin[y]) 34 { 35 qu.push(y); 36 vin[y]=1; 37 } 38 } 39 } 40 } 41 return; 42 } 43 int main() 44 { 45 cin>>n>>m; 46 for(int x,y,ty,tim,i=1;i<=m;i++) 47 { 48 cin>>x>>y>>ty>>tim; 49 adj[x].push_back((node){y,tim}); 50 } 51 spfa(1); 52 for(int i=2;i<=n;i++) 53 { 54 ans=dis[i]; 55 if(ans==2e9) cout<<"-1 "; 56 else cout<<ans<<' '; 57 } 58 return 0; 59 }
SPFA分层图写法
1 #define R 400002 2 #include<iostream> 3 #include<vector> 4 #include<queue> 5 using namespace std; 6 int n,m; 7 struct node 8 { 9 int to,w; 10 }; 11 vector<node>adj[R]; 12 int dis[R],z,w,ans=2e9; 13 bool vin[R]; 14 queue<int>qu; 15 void spfa(int s)//原点s到其他点的最短距离 16 { 17 int x,y,z; 18 for(int i=1;i<=2*n;i++) dis[i]=2e9;//初始都是无穷大（到不了） 19 dis[s]=0;//自己到自己 20 qu.push(s); 21 vin[s]=1; 22 while(qu.size()>0) 23 { 24 x=qu.front(); 25 qu.pop(); 26 vin[x]=0; 27 for(int k=0;k<adj[x].size();k++) 28 { 29 int y=adj[x][k].to; 30 if(dis[y]>dis[x]+adj[x][k].w) 31 { 32 dis[y]=dis[x]+adj[x][k].w; 33 if(!vin[y]) 34 { 35 qu.push(y); 36 vin[y]=1; 37 } 38 } 39 } 40 } 41 return; 42 } 43 int main() 44 { 45 cin>>n>>m; 46 for(int x,y,ty,tim,i=1;i<=m;i++) 47 { 48 cin>>x>>y>>ty>>tim; 49 if(ty==1) 50 { 51 adj[x].push_back((node){y,tim});//第一层： x -> y 52 adj[x+n].push_back((node){y,tim});//第二层： (x+n)->(y+n) 53 } 54 else//跨层连边 55 { 56 adj[x].push_back((node){y+n,tim});//第一层到第二层：x -> y+n 57 } 58 } 59 spfa(1); 60 for(int i=2;i<=n;i++) 61 { 62 ans=min(dis[i],dis[i+n]); 63 if(ans==2e9) cout<<"-1 "; 64 else cout<<ans<<' '; 65 } 66 return 0; 67 }
2025 CSPJ 第一题 多种写法
1 #include<bits/stdc++.h> 2 using namespace std; 3 string a; 4 priority_queue<int>q; 5 int main() 6 { 7 cin>>a; 8 for(int i=0;i<a.size();i++) 9 { 10 if(a[i]>='0'&&a[i]<='9') q.push(a[i]-'0'); 11 } 12 while(q.size()>0) 13 { 14 cout<<q.top(); 15 q.pop(); 16 } 17 return 0; 18 } 19 20 21 #include<bits/stdc++.h> 22 using namespace std; 23 string s; 24 int num[10]; 25 int main() 26 { 27 cin>>s; 28 for(int i=0;i<s.size();i++) 29 { 30 if(s[i]>='0'&&s[i]<='9') num[s[i]-'0']++; 31 } 32 for(int i=9;i>=0;i--) 33 { 34 while(num[i]>0) cout<<i<<' ',num[i]--; 35 } 36 return 0; 37 }
2025 CSPJ 第二题 多种写法
1 #include<bits/stdc++.h> 2 using namespace std; 3 int a[102],n,m; 4 void work() 5 { 6 int x,cnt=0,id,c; 7 cin>>n>>m; 8 cin>>a[1]; 9 x=a[1]; 10 for(int i=2;i<=n*m;i++) 11 { 12 cin>>a[i]; 13 if(a[i]>x) cnt++; 14 } 15 id=cnt+1; 16 sort(a+1,a+1+n*m,greater<int>()); 17 if(id%n==0) c=id/n; 18 else c=id/n+1; 19 w=id-(c-1)*n; 20 if(c%2==1) r=w; 21 else r=n+1-w; 22 cout<<c<<' '<<r<<endl; 23 } 24 int main() 25 { 26 work(); 27 return 0; 28 } 29 30 31 #include<bits/stdc++.h> 32 using namespace std; 33 int a[102],n,m; 34 void work() 35 { 36 int cnt=0; 37 for(int j=1;j<=m;j++) 38 { 39 if(j%2==1) 40 { 41 for(int i=1;i<=n;i++) 42 { 43 id++; 44 if(a[id]==x) cout<<j<<' '<<i<<endl; 45 } 46 } 47 else 48 { 49 for(int i=n;i>=1;i--) 50 { 51 id++; 52 if(a[id]==x) cout<<j<<' '<<i<<endl; 53 } 54 } 55 } 56 } 57 int main() 58 { 59 work(); 60 return 0; 61 }
2025 CSPJ 第三题
1 #include<bits/stdc++.h> 2 using namespace std; 3 //前缀异或 4 //a^b=c --> c^a=b 5 int n,k,a[500001],pos[500001],x,s; 6 int main() 7 { 8 int wei,tou,ans=0,Last;//Last控制它们不许有公共点 9 cin>>n>>k; 10 for(int i=1;i<=n;i++) cin>>a[i]; 11 memset(pos,-1,sizeof pos); 12 pos[0]=0;//边界 "空"的前缀和为0 13 Last=0; 14 for(wei=1;wei<=n;wei++) 15 { 16 s[wei]=s[wei-1]^a[wei]; 17 x=s[wei]^k;//x=s[tou]-1 18 if(pos[x]>=Last) ans++,Last=wei; 19 pos[s[wei]]=wei; 20 } 21 cout<<ans<<endl; 22 return 0; 23 }