A
#include<bits/stdc++.h> #define int long long using namespace std; const int N=1e6+10,mod=2e31-1; int dist[N],cnt[N],res,n,m,s; int e[N],ne[N],w[N],h[N],idx; typedef pair<int,int>pii; bool vis[N]; void add(int a,int b,int c){ e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } void dijkstra() { dist[s]=0; priority_queue<pii,vector<pii>,greater<pii>>que; que.push({0,s}); while(!que.empty()){ auto now=que.top(); que.pop(); int x=now.second,y=now.first; if(vis[x]) continue; vis[x]=true; for(int i=h[x];i!=-1;i=ne[i]){ int j=e[i]; if(dist[j]>y+w[i]){ dist[j]=y+w[i]; que.push({dist[j],j}); } } } } signed main() { cin>>n>>m>>s; memset(h,-1,sizeof h); memset(dist,0x3f,sizeof dist); for(int i=0;i<m;i++){ int a,b,c; cin>>a>>b>>c; add(a,b,c); } dijkstra(); for(int i=1;i<=n;i++) cout<<dist[i]<<' '; return 0; }
B;
#include<bits/stdc++.h> #define int long long using namespace std; const int N=5e4+10; struct node{ int b,w; }e; int n,m,t,cnt[N],dist[N]; vector<node>g[N]; bool vis[N],f; bool spfa() { queue<int>que; que.push(1),cnt[1]=0,dist[1]=0,vis[1]=true; while(!que.empty()){ int now=que.front(); que.pop(); vis[now]=false; for(int i=0;i<g[now].size();i++){ int y=g[now][i].b; if(dist[y]>dist[now]+g[now][i].w){ dist[y]=dist[now]+g[now][i].w; cnt[y]=cnt[now]+1; if(cnt[y]>=n) return true; if(!vis[y]) vis[y]=true,que.push(y); } } } return false; } signed main() { cin>>t; while(t--){ memset(dist,0x3f,sizeof dist); memset(cnt,0,sizeof cnt); memset(vis,false,sizeof vis); cin>>n>>m; for(int i=0;i<=n*2;i++) g[i].clear(); for(int i=0;i<m;i++){ int a,b,c; cin>>a>>b>>c; g[a].push_back({b,c}); if(c>=0) g[b].push_back({a,c}); } if(spfa()) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
C:
#include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+10; int n,m,dist[N],cnt[N],s,res; int e[N],ne[N],h[N],w[N],idx; bool vis[N]; void add(int a,int b,int c) { e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } bool spfa() { queue<int>que; que.push(0),dist[0]=0,vis[0]=true; while(!que.empty()){ int now=que.front(); que.pop(); vis[now]=false,s++; for(int i=h[now];i!=-1;i=ne[i]){ int j=e[i]; if(dist[j]>dist[now]+w[i]){ dist[j]=dist[now]+w[i]; cnt[j]=cnt[now]+1; if(cnt[now]>=n+1) return false; if(!vis[j]) vis[j]=true,que.push(j); } } } return true; } signed main() { memset(h,-1,sizeof h); memset(dist,0x3f,sizeof dist); cin>>n>>m; for(int i=0;i<m;i++){ int a,b,c; cin>>a>>b>>c; add(b,a,c); } for(int i=n;i;i--) add(0,i,1); if(!spfa()) cout<<"NO"<<endl; else for(int i=1;i<=n;i++) cout<<dist[i]<<" "; return 0; }
D:
#include<bits/stdc++.h> #define int long long using namespace std; const int N=200,Max=1e5+10; int n,m,res,num[Max],dist[N][N]; void floyd() { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k]); } signed main() { cin>>n>>m; for(int i=0;i<m;i++) cin>>num[i]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>dist[i][j]; floyd(); int st=1,ed=n; for(int i=0;i<m;i++){ res+=dist[st][num[i]]; st=num[i]; } res+=dist[st][ed]; cout<<res<<endl; return 0; }
E:
#include<bits/stdc++.h> using namespace std; const int N=200; int n,dist[N][N],res,mp[N][N]; int main() { cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>dist[i][j]; for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dist[i][j]=max(dist[i][j],min(dist[i][k],dist[k][j])); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) cout<<dist[i][j]<<" "; cout<<endl; } return 0; }
F:
asdsa
G:
#include<bits/stdc++.h> #define int long long using namespace std; const int N=1e3+10; int n,m,res=0x3f3f3f3f,g[N][N],dist[N],num; bool vis[N]; void floyd() { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=min(g[i][j],g[i][k]+g[k][j]); } signed main() { cin>>n>>m; for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) if(i==j) g[i][j]=0; else g[i][j]=0x3f3f3f3f; for(int i=0;i<m;i++){ int a,b,c; cin>>a>>b>>c; g[a][b]=c,g[b][a]=c; } floyd(); for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++){ num=0; for(int e=1;e<n;e++) for(int k=e+1;k<=n;k++) num+=min(g[e][k],min(g[e][i]+g[j][k],g[e][j]+g[i][k])); res=min(res,num); } cout<<res<<endl; return 0; }
H:
#include<bits/stdc++.h> #define int long long using namespace std; const int N=1e3; int n,m,res,g[N][N]; void floyd() { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=min(g[i][j],g[i][k]+g[k][j]); } signed main() { cin>>n>>m; for(int i=0;i<=n;i++) for(int j=0;j<=n;j++){ g[i][j]=2e9; } for(int i=0;i<m;i++){ int a,b; cin>>a>>b; g[a][b]=1; } floyd(); for(int i=1;i<=n;i++){ int num=0; for(int j=1;j<=n;j++) if((g[j][i]<2e9/2||g[i][j]<2e9/2)&&i!=j) num++; if(num>=n-1) res++; } cout<<res; return 0; }
I:
#include<bits/stdc++.h> //#define int long long using namespace std; const int N=1e6; int p[N],n,m,res,cnt; struct node { int a,b,w; bool operator<(const node&W)const{ return w<W.w; } }edge[N]; int find(int x) { if(x!=p[x]) p[x]=find(p[x]); return p[x]; } signed main() { cin>>n>>m; for(int i=0;i<m;i++){ int a,b,w; cin>>a>>b>>w; edge[i]={a,b,w}; } sort(edge,edge+m); for(int i=1;i<=n;i++) p[i]=i; for(int i=0;i<m;i++){ int a=edge[i].a,b=edge[i].b,w=edge[i].w; if(find(a)!=find(b)) p[find(a)]=find(b),res+=w,cnt++; } if(cnt<n-1) cout<<"orz"<<endl; else cout<<res<<endl; return 0; }
J:
#include<bits/stdc++.h> #define int long long using namespace std; const int N=1e6+10; int n,m,res,cnt,p[N],k,s,t; struct node { int a,b,w; bool operator<(const node&W)const{ return w<W.w; } }q[N]; int find(int x){ if(x!=p[x]) p[x]=find(p[x]); return p[x]; } signed main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>m>>s>>t; for(int i=0;i<m;i++){ int a,b,c; cin>>a>>b>>c; q[i]={a,b,c}; } sort(q,q+m); for(int i=0;i<=n;i++) p[i]=i; for(int i=0;i<m;i++){ int a=q[i].a,b=q[i].b; if(find(a)!=find(b)) res=max(res,q[i].w),p[find(a)]=find(b); if(find(s)==find(t)) return cout<<res<<endl,0; } }
K:
#include<bits/stdc++.h> #define int long long using namespace std; const int N=1e7+10; int n,m,res,p[N],e; bool vis[N]; struct node { int a,b,w; bool operator<(const node&W) const { return w>W.w; } }q[N]; int find(int x) { if(x!=p[x]) p[x]=find(p[x]); return p[x]; } signed main() { cin>>n>>m; for(int i=0;i<m;i++) cin>>e,vis[e]=true; for(int i=1;i<n;i++){ int a,b,c; cin>>a>>b>>c; q[i]={a,b,c},res+=c; } sort(q+1,q+n); for(int i=0;i<=n;i++) p[i]=i; for(int i=1;i<n;i++){ int a=find(q[i].a),b=find(q[i].b); if(vis[a]&&vis[b]) continue; p[a]=b,res-=q[i].w,vis[a]=vis[b]=vis[a]|vis[b]; } cout<<res; return 0; }
L:
#include<bits/stdc++.h> #define int long long using namespace std; const int N=1e6+10; int n,m,res,cnt,p[N],k,num; struct node { int a,b,w; bool operator<(const node&W)const{ return w<W.w; } }q[N]; int find(int x){ if(x!=p[x]) p[x]=find(p[x]); return p[x]; } signed main() { cin>>n>>m>>k; for(int i=0;i<m;i++){ int a,b,c; cin>>a>>b>>c; q[i]={a,b,c}; } sort(q,q+m); for(int i=0;i<=n;i++) p[i]=i; for(int i=0;i<m;i++){ int a=q[i].a,b=q[i].b; if(find(a)!=find(b)){ cnt++; p[find(a)]=find(b); res+=q[i].w; if(cnt>=n-k) break; } } if(cnt<n-k) cout<<"No Answer"<<endl; else cout<<res<<endl; return 0; }