HRBUST1404 Leyni的汽车比赛 题解报告
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了HRBUST1404 Leyni的汽车比赛 题解报告，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1953字，纯文字阅读大概需要3分钟。
内容图文
【题目大意】
【思路分析】
看到问题要求“最少”，于是理所当然地想到DP啦。
设$f[i][j][k]$表示从$i$城到$j$城，途中换了$k$次车所需的最小时间，然后可以想到转移方程：
$$f[i][j][k]=min(f[i][j][k],min\{f[i][t][k-1]+f[t][j][0]\}(1\le t\le n))$$
我们要预处理出$f[i][j][0]$，即$m$种车中从$i$城到$j$城所需的最短时间。我们记$w[i][j][k]$为第$i$种车从$j$城到$k$城所需的最短时间，则$w[i][j][k]=min\{w[i][j][t]+w[i][t][k]\}(1\le t\le n)$，然后可得$f[j][k][0]=min\{w[i][j][k]\}(1\le i\le m)$。
初始值：$w$读入，$f$无穷大。
答案：$min\{f[s][t][i]\}(0\le i\le k)$
代码实现过程中要注意循环的嵌套顺序！
【代码实现】
1 #include<cstdio>
2 #include<iostream>
3 #include<cstring>
4 #include<algorithm>
5 #include<cmath>
6#define g() getchar()
7#define rg register
8#define go(i,a,b) for(rg int i=a;i<=b;i++)
9#define back(i,a,b) for(rg int i=a;i>=b;i--)
10#define db double
11#define ll long long
12#define il inline
13#define pf printf
14#define sf scanf
15#define mem(a,b) memset(a,b,sizeof(a))
16usingnamespace std;
17int fr(){
18int w=0,q=1;
19char ch=g();
20while(ch<‘0‘||ch>‘9‘){
21if(ch==‘-‘) q=-1;
22 ch=g();
23 }
24while(ch>=‘0‘&&ch<=‘9‘) w=(w<<1)+(w<<3)+ch-‘0‘,ch=g();
25return w*q;
26}
27constint N=52;
28const ll INF=1e10+999999999;
29int n,m,r;
30ll f[N][N][N],w[N][N][N],ans;
31int main(){
32//freopen("","r",stdin);
33//freopen("","w",stdout);34while(sf("%d%d%d",&n,&m,&r)!=EOF){
35 mem(f,63);
36 go(i,1,m) go(j,1,n) go(k,1,n) w[i][j][k]=fr();
37//按照输入顺序嵌套循环38 go(i,1,m) go(t,1,n) go(j,1,n) go(k,1,n)
39 w[i][j][k]=min(w[i][j][k],w[i][j][t]+w[i][t][k]);
40//以t为中间点找最小值,Floyd最短路41 go(j,1,n) go(k,1,n) go(i,1,m)
42 f[j][k][0]=min(f[j][k][0],w[i][j][k]);
43//对于固定的两个城市j,k,枚举m种车旭找最短时间44 go(k,1,n) go(t,1,n) go(i,1,n) go(j,1,n)
45 f[i][j][k]=min(f[i][j][k],f[i][t][k-1]+f[t][j][0]);
46//DP,注意循环嵌套的顺序！47while(r--){
48 rg int s=fr(),t=fr(),k=fr();
49if(k>n) k=n;ans=INF;
50 go(i,0,k) ans=min(ans,f[s][t][i]);
51 pf("%lld\n",ans);
52 }
53 }
54return0;
55 }
原文：https://www.cnblogs.com/THWZF/p/11422842.html
内容总结
以上是互联网集市为您收集整理的HRBUST1404 Leyni的汽车比赛 题解报告全部内容，希望文章能够帮你解决HRBUST1404 Leyni的汽车比赛 题解报告所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。