单源最短路的建图

1.热浪

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)http://ybt.ssoier.cn:8088/problem_show.php?pid=1379

很裸的单源最短路问题，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.香甜的黄油

1127. 香甜的黄油 - AcWing题库

枚举每一个农场，然后算一下总距离，然后更新每一个农场的最小值，用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.最优乘车

920. 最优乘车 - AcWing题库https://www.acwing.com/problem/content/description/922/

1. #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.昂贵的聘礼

   903. 昂贵的聘礼 - AcWing题库

   把0当作虚拟起点，假如是直接买的话就与0连条边，假如可以由其他物品替换的话加换的那个物品连被换的物品一条边

   等级制度就枚举一个区间内的等级制度即可。然后求最小值

2. #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);//从虚拟原点连一条边到物品iwhile(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]且长度为mres=min(res,dijkstra(i,i+m));cout<<res<<endl;return 0;
   }