L3-007 天梯地图 (30分) 最短路+dp
2024-10-10 00:03:05
最短路+dp思路：nuoyanli 520 Let‘s play computer game
输入样例1：
10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
5 4 0 2 3
5 9 1 1 4
0 6 0 1 1
7 3 1 1 2
8 3 1 1 2
2 5 0 2 2
2 1 1 1 1
1 5 0 1 3
1 4 0 1 1
9 7 1 1 3
3 1 0 2 5
6 3 1 2 1
5 3
输出样例1：
Time = 6: 5 => 4 => 8 => 3
Distance = 3: 5 => 1 => 3
输入样例2：
7 9
0 4 1 1 1
1 6 1 3 1
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 3 1
3 2 1 2 1
4 5 0 2 2
6 5 1 2 1
3 5
输出样例2：
Time = 3; Distance = 4: 3 => 2 => 5这个nuoyanli 520 Let‘s play computer game 就是讲最短路+dp思路的，它可以满足例如这样的条件 “最快到达路线不唯一，则输出几条最快路线中最短的那条”
这样的话我们就可以采用两边最短路+dp就可以了
代码：
1 #include<iostream>
2 #include<cstdio>
3 #include<cstdlib>
4 #include<cstring>
5 #include<cmath>
6 #include<algorithm>
7 #include<queue>
8 using namespace std;
9 typedef long long ll;
10 typedef unsigned long long ull;
11 const int MAXN=1000000;
12 const int MIN_INF=0x80000000;
13 const int MAX_INF=0x7fffffff;
14 int n,m;
15 int beg[505];
16 int to[505050];
17 int nex[505050];
18 int weight[505050];
19 int tisme[505050];
20 int e;
21 int st,ed;
22 bool vis[505];
23 int answ[505];
24 int anst[505];
25 int stepw[505];
26 int tarw[505];
27 int tart[505];
28 int answw[505];
29 int answwsize;
30 int anstt[505];
31 int ansttsize;
32
33 struct p{
34 int val;
35 int self;
36 int step;
37 bool operator <(const p &b)const{
38 return val>b.val;
39 }
40 };
41
42
43 priority_queue<p> q;
44 void init(){
45 e=0;
46 memset(beg,-1,sizeof(beg));
47 // answw="";
48 // anstt="";
49 return;
50 }
51 //Function area
52
53 void add(int a,int b,int w,int t){
54 nex[++e]=beg[a];
55 beg[a]=e;
56 to[e]=b;
57 weight[e]=w;
58 tisme[e]=t;
59 }
60
61 void Dijkstraw(int start){
62 q.push({0,start,0});
63 memset(vis,0,sizeof(vis));
64 memset(answ,0x3f3f3f3f,sizeof(answ));
65 memset(tarw,-1,sizeof(tarw));
66 memset(stepw,0x3f3f3f3f,sizeof(stepw));
67 answ[start]=0;
68 while(q.size()){
69 p now=q.top();
70 if(now.self==ed)
71 break;
72 q.pop();
73 if(vis[now.self])
74 continue;
75 vis[now.self]=true;
76 for(int i=beg[now.self];i!=-1;i=nex[i]){
77 int nx=to[i];
78 if(answ[nx]>now.val+weight[i]){
79 answ[nx]=now.val+weight[i];
80 q.push({now.val+weight[i],nx,now.step+1});
81 stepw[nx]=now.step+1;
82 tarw[nx]=now.self;
83 }
84 if(answ[nx]==now.val+weight[i]){
85 if(stepw[nx]>now.step+1){
86 q.push({now.val+weight[i],nx,now.step+1});
87 stepw[nx]=now.step+1;
88 tarw[nx]=now.self;
89 }
90 }
91 }
92 }
93 answwsize=0;
94 for(int i=ed;i!=st;i=tarw[i]){
95 answw[++answwsize]=i;
96 }
97 answw[++answwsize]=st;
98 }
99
100 void Dijkstrat(int start){
101 while(q.size())
102 q.pop();
103 q.push({0,start,0});
104 memset(vis,0,sizeof(vis));
105 memset(anst,0x3f3f3f3f,sizeof(anst));
106 memset(answ,0x3f3f3f3f,sizeof(answ));
107 memset(stepw,0x3f3f3f3f,sizeof(stepw));
108 memset(tart,-1,sizeof(tart));
109 answ[start]=0;
110 while(q.size()){
111 p now=q.top();
112 if(now.self==ed)
113 break;
114 q.pop();
115 if(vis[now.self])
116 continue;
117 vis[now.self]=true;
118 for(int i=beg[now.self];i!=-1;i=nex[i]){
119 int nx=to[i];
120 if(anst[nx]>now.val+tisme[i]){
121 anst[nx]=now.val+tisme[i];
122 answ[nx]=now.val+weight[i];
123 q.push({now.val+tisme[i],nx,now.step+1});
124 stepw[nx]=now.step+1;
125 tart[nx]=now.self;
126 }
127 if(anst[nx]==now.val+tisme[i]){
128 if(answ[nx]>now.val+weight[i]){
129 q.push({now.val+tisme[i],nx,now.step+1});
130 tart[nx]=now.self;
131 stepw[nx]=now.step+1;
132 }else if(answ[nx]==now.val+weight[i]){
133 if(stepw[nx]>now.step+1){
134 q.push({now.val+tisme[i],nx,now.step+1});
135 stepw[nx]=now.step+1;
136 tart[nx]=now.self;
137 }
138 }
139 }
140 }
141 }
142 ansttsize=0;
143 for(int i=ed;i!=st;i=tart[i]){
144 anstt[++ansttsize]=i;
145 }
146 anstt[++ansttsize]=st;
147 }
148 int main(){
149 ios::sync_with_stdio(false);
150 ios_base::sync_with_stdio(false);
151 cin.tie(0);
152 cout.tie(0);
153 init();
154 cin>>n>>m;
155 for(int i=1;i<=m;i++){
156 int a,b,c,d,e;
157 cin>>a>>b>>c>>d>>e;
158 if(c==1){
159 add(a,b,d,e);
160 }else{
161 add(a,b,d,e);
162 add(b,a,d,e);
163 }
164 }
165 cin>>st>>ed;
166 Dijkstraw(st);
167 int answww=answ[ed];
168 Dijkstrat(st);
169 cout<<"Time = "<<anst[ed];
170 bool flagttt=true;
171 if(answwsize==ansttsize){
172 for(int i=1;i<=answwsize;i++){
173 if(answw[i]!=anstt[i]){
174 flagttt=false;
175 break;
176 }
177 }
178 }else{
179 flagttt=false;
180 }
181 if(flagttt==true){
182 cout<<"; Distance = "<<answww;
183 cout<<": ";
184 // reverse(answw.begin(),answw.end());
185 for(int i=answwsize;i!=0;i--){
186 if(i!=answwsize)
187 cout<<" => ";
188 cout<<answw[i];
189 }
190 cout<<endl;
191 }else{
192 cout<<": ";
193 for(int i=ansttsize;i!=0;i--){
194 if(i!=ansttsize)
195 cout<<" => ";
196 cout<<anstt[i];
197 }
198 cout<<endl;
199 cout<<"Distance = "<<answww;
200 cout<<": ";
201 for(int i=answwsize;i!=0;i--){
202 if(i!=answwsize)
203 cout<<" => ";
204 cout<<answw[i];
205 }
206 cout<<endl;
207 }
208 }
不知道为啥我的这个代码错了一组样例（23分）
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<algorithm>
5 #include<queue>
6 #include<vector>
7 using namespace std;
8 const int maxn=505;
9 #define INF 0x3f3f3f3f
10 struct shudui1
11 {
12 int start,value;
13 bool operator < (const shudui1 q)const
14 {
15 return value>q.value;
16 }
17 } str1;
18 struct shudui2
19 {
20 int start,value1,value2;
21 } str2;
22 int dis[maxn],path[maxn],dp[maxn],path1[maxn],vis[maxn],path2[maxn],len1,len2;
23 priority_queue<shudui1>r; //里面的数据默认是从小到大排序，这样就不用通过佛如循环遍历在每一次找v里面的最小值
24 vector <shudui2>w[maxn]; //将每一个起点的值作为数组的标识
25 //例如，1 2 3这一组数据，就是说1连接着2，那就把所有1能到的地方存到这个里面
26 void JK1(int s,int en)
27 {
28 memset(dp,INF,sizeof(dp));
29 memset(dis,INF,sizeof(dis));
30 memset(vis,0,sizeof(vis));
31 memset(path,-1,sizeof(path));
32 dp[s]=0;
33 dis[s]=0;
34 str1.start=s;
35 str1.value=0;
36 r.push(str1);
37 while(!r.empty())
38 {
39 int x,y;
40 str1=r.top();
41 r.pop();
42 x=str1.start;
43 y=str1.value;
44 if(vis[x]) continue;
45 vis[x]=1;
46 int len=w[x].size();
47 for(int i=0; i<len; ++i)
48 {
49 str2=w[x][i];
50 if(dis[x]+str2.value1<dis[str2.start])
51 {
52
53 dp[str2.start]=dp[x]+str2.value2;
54 dis[str2.start]=dis[x]+str2.value1;
55 path[str2.start]=x;
56 //printf("%d %d***\n",str2.start,x);
57 if(!vis[str2.start])
58 {
59 str1.start=str2.start;
60 str1.value=dis[str2.start];
61 r.push(str1);
62 }
63
64 }
65 else if(dis[x]+str2.value1==dis[str2.start])
66 {
67 if(dp[str2.start]>dp[x]+str2.value2)
68 {
69 //printf("%d %d***\n",str2.start,x);
70 path[str2.start]=x;
71 dp[str2.start]=dp[x]+str2.value2;
72 if(!vis[str2.start])
73 {
74 str1.start=str2.start;
75 str1.value=dis[str2.start];
76 r.push(str1);
77 }
78 }
79 }
80 }
81 }
82 }
83 void JK2(int s,int en)
84 {
85 memset(dp,INF,sizeof(dp));
86 memset(dis,INF,sizeof(dis));
87 memset(vis,0,sizeof(vis));
88 memset(path,-1,sizeof(path));
89 dp[s]=0;
90 dis[s]=0;
91 str1.start=s;
92 str1.value=0;
93 r.push(str1);
94 while(!r.empty())
95 {
96 int x,y;
97 str1=r.top();
98 r.pop();
99 x=str1.start;
100 y=str1.value;
101 if(vis[x]) continue;
102 vis[x]=1;
103 int len=w[x].size();
104 for(int i=0; i<len; ++i)
105 {
106 str2=w[x][i];
107 if(dis[x]+str2.value2<dis[str2.start])
108 {
109
110 dp[str2.start]=dp[x]+str2.value1;
111 dis[str2.start]=dis[x]+str2.value2;
112 path[str2.start]=x;
113 //printf("%d %d***\n",str2.start,x);
114 // if(!vis[str2.start])
115 // {
116 str1.start=str2.start;
117 str1.value=dis[str2.start];
118 r.push(str1);
119 // }
120
121 }
122 else if(dis[x]+str2.value2==dis[str2.start])
123 {
124 if(dp[str2.start]>dp[x]+str2.value1)
125 {
126 //printf("%d %d***\n",str2.start,x);
127 path[str2.start]=x;
128 dp[str2.start]=dp[x]+str2.value1;
129 // if(!vis[str2.start])
130 // {
131 str1.start=str2.start;
132 str1.value=dis[str2.start];
133 r.push(str1);
134 // }
135 }
136 }
137 }
138 }
139 }
140 int main()
141 {
142 int n,m;
143 scanf("%d%d",&n,&m);
144 while(m--)
145 {
146 int x,y,z1,z2,type;
147 scanf("%d%d%d%d%d",&x,&y,&type,&z1,&z2);
148 x++;
149 y++;
150 if(type)
151 {
152 //p[x][y]=z2;
153 str2.start=y;
154 str2.value1=z1;
155 str2.value2=z2;
156 w[x].push_back(str2);
157 }
158 else
159 {
160 //p[x][y]=p[y][x]=z2;
161 str2.start=y;
162 str2.value1=z1;
163 str2.value2=z2;
164 w[x].push_back(str2);
165 str2.start=x;
166 w[y].push_back(str2);
167 }
168 }
169 int st,en,short_dis,short_time;
170 scanf("%d%d",&st,&en);
171 st++;en++;
172 JK1(st,en);
173 short_dis=dis[en];
174 int temp=en;
175 while(temp!=-1)
176 {
177 path1[len1++]=temp;
178 temp=path[temp];
179 }
180
181 JK2(st,en);
182 short_time=dis[en];
183 temp=en;
184 while(temp!=-1)
185 {
186 path2[len2++]=temp;
187 temp=path[temp];
188 }
189 int flag=0;
190 if(len1==len2)
191 {
192 for(int i=0; i<len1; ++i)
193 {
194 if(path1[i]!=path2[i])
195 {
196 flag=1;
197 break;
198 }
199 }
200 }
201 else flag=1;
202
203 if(flag)
204 {
205 printf("Time = %d: %d",short_time,st-1);
206 for(int i=len2-2; i>=0; --i)
207 {
208 printf(" => %d",path2[i]-1);
209 }
210 printf("\n");
211
212 printf("Distance = %d: %d",short_dis,st-1);
213 for(int i=len1-2; i>=0; --i)
214 {
215 printf(" => %d",path1[i]-1);
216 }
217 printf("\n");
218 }
219 else
220 {
221 printf("Time = %d; Distance = %d: %d",short_time,short_dis,st-1);
222 for(int i=len1-2; i>=0; --i)
223 {
224 printf(" => %d",path1[i]-1);
225 }
226 printf("\n");
227 }
228 return 0;
229 }
最新文章
- 了解PHP中的Array数组和foreach
- pythonchallenge 解谜 Level 2
- 烂泥：CentOS安装及配置TFTP服务器
- Tomcat遇到”Error listenerStart”或”Error filterStart”问题且无详细日志时的log配置.
- 剑指Offer14 逆序链表
- VC中监测函数运行时间（一）—分钟，秒，毫秒
- [MODx] 9. Real Example
- Spring--------web应用中保存spring容器
- XX秘籍
- 深度优先搜索(DFS)递归形式改为非递归形式
- ARP欺骗分析
- JavaWeb-SQL-Servlet-JSP学做购物系统——日志一
- ssh 端口更改或ssh 远程接不上的问题（尤其是国外服务器）
- 7款不错的 CI/CD工具
- (7)Jquery1.8.3快速入门_内容过滤选择器
- Android自定义View学习（四）
- BZOJ 4129 Haruna’s Breakfast (分块 + 带修莫队)
- android中的ellipsize
- java基础讲解10-----类的高级特性
- How to reference two table when lack reference column.