1.热浪
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
很裸的单源最短路问题，n=2500,可以用dijksta或者spfa都能过，下面展示spfa的做法
#include<bits/stdc++.h> using namespace std; const int N=2510,M=6200*2+10; int h[N],e[M],ne[M],w[M],idx; int dist[N]; bool st[N]; int S,E; void add(int a,int b,int c) { w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int spfa() { memset(dist,0x3f,sizeof dist); dist[S]=0; queue<int> q; q.push(S); st[S]=true; while(q.size()) { int t=q.front(); q.pop(); st[t]=false; for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(dist[j]>dist[t]+w[i]) { dist[j]=dist[t]+w[i]; if(!st[j]) { q.push(j); st[j]=true; } } } } return dist[E]; } int main() { int T,m; cin>>T>>m>>S>>E; memset(h,-1,sizeof h); for(int i=0;i<m;i++) { int a,b,c; cin>>a>>b>>c; add(a,b,c),add(b,a,c); } cout<<spfa()<<endl; return 0; }
2.信使
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
由于数据较小可以用Floyd算法求两两之间的最短路，然后后面更新一遍一号点到每一个点的最小距离即可
#include<bits/stdc++.h> using namespace std; const int N=110; int dist[N][N]; int n,m; int flyd() { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]); int ans=0; for(int i=2;i<=n;i++) ans=max(dist[1][i],ans); return ans; } int main() { cin>>n>>m; memset(dist,0x3f,sizeof dist); for(int i=0;i<m;i++) { int a,b,c; cin>>a>>b>>c; dist[a][b]=dist[b][a]=min(dist[a][b],c); } int t=flyd(); if(t==0x3f3f3f3f) puts("-1"); else cout<<t<<endl; return 0; }
3.香甜的黄油
枚举每一个农场，然后算一下总距离，然后更新每一个农场的最小值，用spfa求最小距离
#include<bits/stdc++.h> using namespace std; const int N=810,M=3000; int h[N],e[M],ne[M],w[M],idx; int id[N],dist[N]; int n,p,c; bool st[N]; void add(int a,int b,int c) { w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int spfa(int s) { memset(dist,0x3f,sizeof dist); memset(st,0,sizeof st); queue<int> q; q.push(s); dist[s]=0; st[s]=true; while(q.size()) { int t=q.front(); q.pop(); st[t]=false; for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(dist[j]>dist[t]+w[i]) { dist[j]=dist[t]+w[i]; if(!st[j]) { q.push(j); st[j]=true; } } } } int ans=0; for(int i=1;i<=n;i++) { int j=id[i]; if(dist[j]==0x3f3f3f3f) return 0x3f3f3f3f; ans+=dist[j]; } return ans; } int main() { cin>>n>>p>>c; memset(h,-1,sizeof h); for(int i=1;i<=n;i++) cin>>id[i]; for(int i=0;i<c;i++) { int a,b,c; cin>>a>>b>>c; add(a,b,c),add(b,a,c); } int ans=0x3f3f3f3f; for(int i=1;i<=p;i++) ans=min(ans,spfa(i)); cout<<ans<<endl; return 0; }
4.最小花费
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
算乘法的最短路，也就是把加法改成乘法即可，在求乘的最大值，dist初始化为0就行，用spfa可以过
#include<bits/stdc++.h> using namespace std; const int N=2010,M=2e5+10; int h[N],e[M],ne[M],idx; double w[M]; double dist[N]; int n,m; int A,B; bool st[N]; void add(int a,int b,double c) { w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++; } double spfa() { queue<int> q; q.push(A); dist[A]=1; st[A]=true; while(q.size()) { int t=q.front(); q.pop(); st[t]=false; for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(dist[j]<dist[t]*w[i]) { dist[j]=dist[t]*w[i]; if(!st[j]) { q.push(j); st[j]=true; } } } } return dist[B]; } int main() { cin>>n>>m; memset(h,-1,sizeof h); for(int i=0;i<m;i++) { int a,b; double c; cin>>a>>b>>c; c=(100-c)/100; add(a,b,c),add(b,a,c); } cin>>A>>B; double ans=100.0/spfa(); printf("%.8lf",ans); return 0; }
5.最优乘车
#include<bits/stdc++.h> using namespace std; const int N=510; int stop[N]; int dist[N]; bool g[N][N]; int m,n; int q[N]; int bfs()//用bfs求最短路，因为边权只有0 1.0表示不能乘坐的到，1表示能乘坐的到 { memset(dist,0x3f,sizeof dist); dist[1]=0; q[0]=1; int hh=0,tt=0; while(hh<=tt) { int t=q[hh++]; for(int i=1;i<=n;i++) if(g[t][i]&&dist[i]>dist[t]+1) { dist[i]=dist[t]+1; q[++tt]=i; } } return dist[n]; } int main() { cin>>m>>n; string line; getline(cin,line); while(m--) { getline(cin,line); stringstream ssin(line); int cnt=0,p; while(ssin>>p) stop[cnt++]=p; //将每个站点都连起来，说明有一条路能够通往 for(int i=0;i<cnt;i++) for(int j=i+1;j<cnt;j++) g[stop[i]][stop[j]]=true; } int t=bfs(); if(t==0x3f3f3f3f) puts("NO"); else cout<<bfs()-1<<endl; return 0; }
6.昂贵的聘礼
把0当作虚拟起点，假如是直接买的话就与0连条边，假如可以由其他物品替换的话加换的那个物品连被换的物品一条边
等级制度就枚举一个区间内的等级制度即可。然后求最小值
#include<bits/stdc++.h> using namespace std; const int N=110; int m,n; int w[N][N],level[N]; bool st[N]; int dist[N]; int dijkstra(int down,int up)//一个是最小等级，一个是最大等级 { memset(dist,0x3f,sizeof dist); memset(st,0,sizeof st); dist[0]=0; for(int i=1;i<=n;i++) { int t=-1; for(int j=0;j<=n;j++) if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j; if(st[t]) continue; st[t]=true; for(int j=1;j<=n;j++) if(level[j]>=down&&level[j]<=up)//等级得在这个范围 dist[j]=min(dist[j],dist[t]+w[t][j]); } return dist[1];//返回购买第一个物品的最小值 } int main() { cin>>m>>n; memset(w,0x3f,sizeof w); for(int i=1;i<=n;i++) w[i][i]=0; for(int i=1;i<=n;i++) { int p,cnt; cin>>p>>level[i]>>cnt; w[0][i]=min(w[0][i],p);//从虚拟原点连一条边到物品i while(cnt--)//替代物 { int id,cost; cin>>id>>cost; w[id][i]=min(w[id][i],cost);//从替代物连一条边到该物品 } } int res=0x3f3f3f3f; for(int i=level[1]-m;i<=level[1];i++)//最小枚举level[1]-m,最大枚举level[1],因为要覆盖level[1]且长度为m res=min(res,dijkstra(i,i+m)); cout<<res<<endl; return 0; }
