电影网站怎么建设,六盘水市城乡建设局网站,壁纸网站模板,黄山旅游必去十大景点1.热浪
信息学奥赛一本通#xff08;C版#xff09;在线评测系统 (ssoier.cn)http://ybt.ssoier.cn:8088/problem_show.php?pid1379
很裸的单源最短路问题#xff0c;n2500,可以用dijksta或者spfa都能过#xff0c;下面展示spfa的做法
#includebits/stdc.h
usi…1.热浪
信息学奥赛一本通C版在线评测系统 (ssoier.cn)http://ybt.ssoier.cn:8088/problem_show.php?pid1379
很裸的单源最短路问题n2500,可以用dijksta或者spfa都能过下面展示spfa的做法
#includebits/stdc.h
using namespace std;
const int N2510,M6200*210;
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;queueint q;q.push(S);st[S]true;while(q.size()){int tq.front();q.pop();st[t]false;for(int ih[t];~i;ine[i]){int je[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;cinTmSE;memset(h,-1,sizeof h);for(int i0;im;i){int a,b,c;cinabc;add(a,b,c),add(b,a,c);}coutspfa()endl;return 0;
} 2.信使
信息学奥赛一本通C版在线评测系统 (ssoier.cn)
由于数据较小可以用Floyd算法求两两之间的最短路然后后面更新一遍一号点到每一个点的最小距离即可
#includebits/stdc.h
using namespace std;
const int N110;
int dist[N][N];
int n,m;
int flyd()
{for(int k1;kn;k)for(int i1;in;i)for(int j1;jn;j)dist[i][j]min(dist[i][j],dist[i][k]dist[k][j]);int ans0;for(int i2;in;i) ansmax(dist[1][i],ans);return ans;
}
int main()
{cinnm;memset(dist,0x3f,sizeof dist);for(int i0;im;i){int a,b,c;cinabc;dist[a][b]dist[b][a]min(dist[a][b],c);}int tflyd();if(t0x3f3f3f3f) puts(-1);else couttendl;return 0;
}
3.香甜的黄油
1127. 香甜的黄油 - AcWing题库
枚举每一个农场然后算一下总距离然后更新每一个农场的最小值用spfa求最小距离
#includebits/stdc.h
using namespace std;
const int N810,M3000;
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);queueint q;q.push(s);dist[s]0;st[s]true;while(q.size()){int tq.front();q.pop();st[t]false;for(int ih[t];~i;ine[i]){int je[i];if(dist[j]dist[t]w[i]){dist[j]dist[t]w[i];if(!st[j]){q.push(j);st[j]true;}}}}int ans0;for(int i1;in;i){int jid[i];if(dist[j]0x3f3f3f3f) return 0x3f3f3f3f;ansdist[j];}return ans;
}
int main()
{cinnpc;memset(h,-1,sizeof h);for(int i1;in;i) cinid[i];for(int i0;ic;i){int a,b,c;cinabc;add(a,b,c),add(b,a,c);}int ans0x3f3f3f3f;for(int i1;ip;i) ansmin(ans,spfa(i));coutansendl;return 0;
} 4.最小花费
信息学奥赛一本通C版在线评测系统 (ssoier.cn)
算乘法的最短路也就是把加法改成乘法即可在求乘的最大值dist初始化为0就行用spfa可以过
#includebits/stdc.h
using namespace std;
const int N2010,M2e510;
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()
{queueint q;q.push(A);dist[A]1;st[A]true;while(q.size()){int tq.front();q.pop();st[t]false;for(int ih[t];~i;ine[i]){int je[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()
{cinnm;memset(h,-1,sizeof h);for(int i0;im;i){int a,b;double c;cinabc;c(100-c)/100;add(a,b,c),add(b,a,c);}cinAB;double ans100.0/spfa();printf(%.8lf,ans);return 0;
} 5.最优乘车
920. 最优乘车 - AcWing题库https://www.acwing.com/problem/content/description/922/ #includebits/stdc.h
using namespace std;
const int N510;
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 hh0,tt0;while(hhtt){int tq[hh];for(int i1;in;i)if(g[t][i]dist[i]dist[t]1){dist[i]dist[t]1;q[tt]i;}}return dist[n];
}
int main()
{cinmn;string line;getline(cin,line);while(m--){getline(cin,line);stringstream ssin(line);int cnt0,p;while(ssinp) stop[cnt]p;//将每个站点都连起来说明有一条路能够通往for(int i0;icnt;i)for(int ji1;jcnt;j)g[stop[i]][stop[j]]true;}int tbfs();if(t0x3f3f3f3f) puts(NO);else coutbfs()-1endl;return 0;
} 6.昂贵的聘礼 903. 昂贵的聘礼 - AcWing题库 把0当作虚拟起点假如是直接买的话就与0连条边假如可以由其他物品替换的话加换的那个物品连被换的物品一条边 等级制度就枚举一个区间内的等级制度即可。然后求最小值 #includebits/stdc.h
using namespace std;
const int N110;
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 i1;in;i){int t-1;for(int j0;jn;j)if(!st[j](t-1||dist[j]dist[t]))tj;if(st[t]) continue;st[t]true;for(int j1;jn;j)if(level[j]downlevel[j]up)//等级得在这个范围dist[j]min(dist[j],dist[t]w[t][j]);}return dist[1];//返回购买第一个物品的最小值
}
int main()
{cinmn;memset(w,0x3f,sizeof w);for(int i1;in;i) w[i][i]0;for(int i1;in;i){int p,cnt;cinplevel[i]cnt;w[0][i]min(w[0][i],p);//从虚拟原点连一条边到物品iwhile(cnt--)//替代物{int id,cost;cinidcost;w[id][i]min(w[id][i],cost);//从替代物连一条边到该物品}}int res0x3f3f3f3f;for(int ilevel[1]-m;ilevel[1];i)//最小枚举level[1]-m,最大枚举level[1],因为要覆盖level[1]且长度为mresmin(res,dijkstra(i,im));coutresendl;return 0;
}
