当前位置：首页 > news >正文

0102

news 2026/4/10 17:35:12

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 }

View Code

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 }

View Code

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 }

View Code

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 }

View Code

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 }