L3-007 天梯地图（Dijkstra(两边权+一边权一点权)）

159 阅读 0 评论 105 点赞

我是靠谱客的博主壮观面包，这篇文章主要介绍L3-007 天梯地图（Dijkstra(两边权+一边权一点权)），现在分享给大家，希望可以做个参考。

题目链接：L3-007 天梯地图
考查知识：Dijkstra(两边权+一边权一点权)
题意描述：
- 给定n个地点和m条道路，按以下要求任意给定两点间距离。
- 如果最快到达路线不唯一，则输出几条最快路线中最短的那条，题目保证这条路线是唯一的。
- 而如果最短距离的路线不唯一，则输出途径节点数最少的那条，题目保证这条路线是唯一的。
思路简析：根据题意两遍dijkstra，第一遍是第一标尺时间（边权），第二标尺距离（边权）；第二遍第一标尺距离（边权），第二标尺点数（点权）；然后比较两个路径序列即可
- 需要注意的是第一遍dijkstra的第二标尺的选择是 $e [u] [j] < e [p r e [j]] [j]$ 而不是 $d [u] + e [u] [j] < d [j]$

具体代码

复制代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e2+100,inf=0x3fffffff;
int vis[N],d[N],e[N][N],pre[N],p[N],t[N][N],pre2[N],num[N],pre3[N];
void dijkstra(int n,int s){
vis[s]=1;
for(int i=0;i<n-1;i++){
int u=-1,mi=inf;//找与起点联通的点中未访问的且边权最小的点[1,n] 
for(int j=0;j<n;j++){//编号[0,n) 
if(!vis[j]&&p[j]<mi){
u=j;
mi=p[j];
}
}
if(u==-1)break;
else vis[u]=1;
for(int j=0;j<n;j++){//找通过该中介点与起点联通的点中未访问的且可更新对应边权的点，更新其对应的最小边权[1,n] 
if(!vis[j]&&p[u]+t[u][j]<p[j]){
p[j]=p[u]+t[u][j];
pre[j]=u;
}else if(!vis[j]&&p[u]+t[u][j]==p[j]){
if(e[u][j]<e[pre[j]][j]){//注意不是d[u]+e[u][j]<d[j]
p[j]=p[u]+t[u][j];
pre[j]=u;
}
}
}
}
}
void dijkstra2(int n,int s){
vis[s]=1;
for(int i=0;i<n-1;i++){
int u=-1,mi=inf;//找与起点联通的点中未访问的且边权最小的点[1,n] 
for(int j=0;j<n;j++){//编号[0,n) 
if(!vis[j]&&d[j]<mi){
u=j;
mi=d[j];
}
}
if(u==-1)break;
else vis[u]=1;
for(int j=0;j<n;j++){//找通过该中介点与起点联通的点中未访问的且可更新对应边权的点，更新其对应的最小边权[1,n] 
if(!vis[j]&&d[u]+e[u][j]<d[j]){
d[j]=d[u]+e[u][j];
pre2[j]=u;
num[j]=num[u]+1;
}else if(!vis[j]&&d[u]+e[u][j]==d[j]){
if(num[u]+1<num[j]){
num[j]=num[u]+1;
pre2[j]=u;
}
}
}
}
}
int judge(int a[],int n,int b[],int m){
if(n!=m)return 0;
else{
for(int i=0;i<n;i++){
if(a[i]!=b[i])return 0;
}
return 1;
}
}
int main(){
ios::sync_with_stdio;
cin.tie(0),cout.tie(0);
int n,m,s,v;
cin>>n>>m;
for(int i=0;i<n;i++){//无向图初始化 
for(int j=0;j<n;j++){
if(i!=j){
e[i][j]=e[j][i]=inf;
t[i][j]=t[j][i]=inf;
}
}
}
int x,y,z,w,q;
while(m--){//读入边 
cin>>x>>y>>z>>w>>q;
e[x][y]=w,t[x][y]=q;
if(!z)e[y][x]=w,t[y][x]=q;
}
cin>>s>>v;//起点，终点 
for(int i=0;i<n;i++){
d[i]=e[s][i],p[i]=t[s][i];
}
memset(pre,-1,sizeof(pre));
dijkstra(n,s);
memset(vis,0,sizeof(vis));
memset(pre2,-1,sizeof(pre2));
dijkstra2(n,s);
int cn=0,cn2=0,road[N],road2[N],k=v,l=v;
while(k!=-1){
road[cn++]=k;
k=pre[k];
}
while(l!=-1){
road2[cn2++]=l;
l=pre2[l];
}
int mit=p[v],mid=d[v];//最短时间 
if(judge(road,cn,road2,cn2)){
cout<<"Time = "<<mit<<"; Distance = "<<mid<<": "<<s;
for(int i=cn-1;i>=0;i--){
cout<<" => "<<road[i];
}
}else{
cout<<"Time = "<<mit<<": "<<s;
for(int i=cn-1;i>=0;i--){
cout<<" => "<<road[i];
}
cout<<endl;
cout<<"Distance = "<<mid<<": "<<s;
for(int i=cn2-1;i>=0;i--){
cout<<" => "<<road2[i];
}
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e2+100,inf=0x3fffffff;
int vis[N],d[N],e[N][N],pre[N],p[N],t[N][N],pre2[N],num[N],pre3[N];
void dijkstra(int n,int s){
vis[s]=1;
for(int i=0;i<n-1;i++){
int u=-1,mi=inf;//找与起点联通的点中未访问的且边权最小的点[1,n] 
for(int j=0;j<n;j++){//编号[0,n) 
if(!vis[j]&&p[j]<mi){
u=j;
mi=p[j];
}
}
if(u==-1)break;
else vis[u]=1;
for(int j=0;j<n;j++){//找通过该中介点与起点联通的点中未访问的且可更新对应边权的点，更新其对应的最小边权[1,n] 
if(!vis[j]&&p[u]+t[u][j]<p[j]){
p[j]=p[u]+t[u][j];
pre[j]=u;
}else if(!vis[j]&&p[u]+t[u][j]==p[j]){
if(e[u][j]<e[pre[j]][j]){//注意不是d[u]+e[u][j]<d[j]
p[j]=p[u]+t[u][j];
pre[j]=u;
}
}
}
}
}
void dijkstra2(int n,int s){
vis[s]=1;
for(int i=0;i<n-1;i++){
int u=-1,mi=inf;//找与起点联通的点中未访问的且边权最小的点[1,n] 
for(int j=0;j<n;j++){//编号[0,n) 
if(!vis[j]&&d[j]<mi){
u=j;
mi=d[j];
}
}
if(u==-1)break;
else vis[u]=1;
for(int j=0;j<n;j++){//找通过该中介点与起点联通的点中未访问的且可更新对应边权的点，更新其对应的最小边权[1,n] 
if(!vis[j]&&d[u]+e[u][j]<d[j]){
d[j]=d[u]+e[u][j];
pre2[j]=u;
num[j]=num[u]+1;
}else if(!vis[j]&&d[u]+e[u][j]==d[j]){
if(num[u]+1<num[j]){
num[j]=num[u]+1;
pre2[j]=u;
}
}
}
}
}
int judge(int a[],int n,int b[],int m){
if(n!=m)return 0;
else{
for(int i=0;i<n;i++){
if(a[i]!=b[i])return 0;
}
return 1;
}
}
int main(){
ios::sync_with_stdio;
cin.tie(0),cout.tie(0);
int n,m,s,v;
cin>>n>>m;
for(int i=0;i<n;i++){//无向图初始化 
for(int j=0;j<n;j++){
if(i!=j){
e[i][j]=e[j][i]=inf;
t[i][j]=t[j][i]=inf;
}
}
}
int x,y,z,w,q;
while(m--){//读入边 
cin>>x>>y>>z>>w>>q;
e[x][y]=w,t[x][y]=q;
if(!z)e[y][x]=w,t[y][x]=q;
}
cin>>s>>v;//起点，终点 
for(int i=0;i<n;i++){
d[i]=e[s][i],p[i]=t[s][i];
}
memset(pre,-1,sizeof(pre));
dijkstra(n,s);
memset(vis,0,sizeof(vis));
memset(pre2,-1,sizeof(pre2));
dijkstra2(n,s);
int cn=0,cn2=0,road[N],road2[N],k=v,l=v;
while(k!=-1){
road[cn++]=k;
k=pre[k];
}
while(l!=-1){
road2[cn2++]=l;
l=pre2[l];
}
int mit=p[v],mid=d[v];//最短时间 
if(judge(road,cn,road2,cn2)){
cout<<"Time = "<<mit<<"; Distance = "<<mid<<": "<<s;
for(int i=cn-1;i>=0;i--){
cout<<" => "<<road[i];
}
}else{
cout<<"Time = "<<mit<<": "<<s;
for(int i=cn-1;i>=0;i--){
cout<<" => "<<road[i];
}
cout<<endl;
cout<<"Distance = "<<mid<<": "<<s;
for(int i=cn2-1;i>=0;i--){
cout<<" => "<<road2[i];
}
}
return 0;
}

用到了两次dijkstra，是因为据题意，两条路径的第一标尺不一样，所以无法根据传统的第一二三标尺依次去选择最佳路径
但是也可以强行把两个dijkstra的代码合到一起，代码量略少一点 (;￢д￢)，可以交换数组+标记变量实现

复制代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e2+100,inf=0x3fffffff;
int vis[N],d[N],e[N][N],pre[N],p[N],t[N][N],pre2[N],num[N],flag=1;
void dijkstra(int n,int s){
vis[s]=1;
for(int i=0;i<n-1;i++){
int u=-1,mi=inf;//找与起点联通的点中未访问的且距离最近的点[1,n] 
for(int j=0;j<n;j++){//编号[0,n) 
if(!vis[j]&&p[j]<mi){
u=j;
mi=p[j];
}
}
if(u==-1)break;//如果没有与起点联通的点了，则算法结束 
else vis[u]=1;//标记该点已访问
for(int j=0;j<n;j++){//找通过该中介点与起点联通的点中未访问的且可更新对应边权的点，更新其对应的最小边权[1,n] 
if(!vis[j]&&p[u]+t[u][j]<p[j]){
p[j]=p[u]+t[u][j];
num[j]=num[u]+1;
if(flag)pre[j]=u;
else pre2[j]=u;
}else if(!vis[j]&&p[u]+t[u][j]==p[j]){
if(flag&&e[u][j]<e[pre[j]][j]){
p[j]=p[u]+t[u][j];
pre[j]=u;//题目保证这条路线是唯一的,所以不用担心被下面的pre[j]=u影响 
}
if(!flag&&num[u]+1<num[j]){
num[j]=num[u]+1;
pre2[j]=u;
}
}
}
}
}
int judge(int a[],int n,int b[],int m){
if(n!=m)return 0;
else{
for(int i=0;i<n;i++){
if(a[i]!=b[i])return 0;
}
return 1;
}
}
int main(){
ios::sync_with_stdio;
cin.tie(0),cout.tie(0);
int n,m,s,v;
cin>>n>>m;
for(int i=0;i<n;i++){//无向图初始化 
for(int j=0;j<n;j++){
if(i!=j){
e[i][j]=e[j][i]=inf;
t[i][j]=t[j][i]=inf;
}
}
}
int x,y,z,w,q;
while(m--){//读入边 
cin>>x>>y>>z>>w>>q;
e[x][y]=w,t[x][y]=q;
if(!z)e[y][x]=w,t[y][x]=q;
}
cin>>s>>v;//起点，终点 
for(int i=0;i<n;i++){
d[i]=e[s][i],p[i]=t[s][i];
}
memset(pre,-1,sizeof(pre));
dijkstra(n,s);
flag=0;
swap(d,p);swap(e,t);
memset(vis,0,sizeof(vis));
memset(num,0,sizeof(num));
memset(pre2,-1,sizeof(pre2));
dijkstra(n,s);
int cn=0,cn2=0,road[N],road2[N],k=v,l=v;
while(k!=-1){
road[cn++]=k;
k=pre[k];
}
while(l!=-1){
road2[cn2++]=l;
l=pre2[l];
}
int mit=d[v];//最短时间
int mid=p[v];
if(judge(road,cn,road2,cn2)){
cout<<"Time = "<<mit<<"; Distance = "<<mid<<": "<<s;
for(int i=cn-1;i>=0;i--){
cout<<" => "<<road[i];
}
}else{
cout<<"Time = "<<mit<<": "<<s;
for(int i=cn-1;i>=0;i--){
cout<<" => "<<road[i];
}
cout<<endl;
cout<<"Distance = "<<mid<<": "<<s;
for(int i=cn2-1;i>=0;i--){
cout<<" => "<<road2[i];
}
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e2+100,inf=0x3fffffff;
int vis[N],d[N],e[N][N],pre[N],p[N],t[N][N],pre2[N],num[N],flag=1;
void dijkstra(int n,int s){
vis[s]=1;
for(int i=0;i<n-1;i++){
int u=-1,mi=inf;//找与起点联通的点中未访问的且距离最近的点[1,n] 
for(int j=0;j<n;j++){//编号[0,n) 
if(!vis[j]&&p[j]<mi){
u=j;
mi=p[j];
}
}
if(u==-1)break;//如果没有与起点联通的点了，则算法结束 
else vis[u]=1;//标记该点已访问
for(int j=0;j<n;j++){//找通过该中介点与起点联通的点中未访问的且可更新对应边权的点，更新其对应的最小边权[1,n] 
if(!vis[j]&&p[u]+t[u][j]<p[j]){
p[j]=p[u]+t[u][j];
num[j]=num[u]+1;
if(flag)pre[j]=u;
else pre2[j]=u;
}else if(!vis[j]&&p[u]+t[u][j]==p[j]){
if(flag&&e[u][j]<e[pre[j]][j]){
p[j]=p[u]+t[u][j];
pre[j]=u;//题目保证这条路线是唯一的,所以不用担心被下面的pre[j]=u影响 
}
if(!flag&&num[u]+1<num[j]){
num[j]=num[u]+1;
pre2[j]=u;
}
}
}
}
}
int judge(int a[],int n,int b[],int m){
if(n!=m)return 0;
else{
for(int i=0;i<n;i++){
if(a[i]!=b[i])return 0;
}
return 1;
}
}
int main(){
ios::sync_with_stdio;
cin.tie(0),cout.tie(0);
int n,m,s,v;
cin>>n>>m;
for(int i=0;i<n;i++){//无向图初始化 
for(int j=0;j<n;j++){
if(i!=j){
e[i][j]=e[j][i]=inf;
t[i][j]=t[j][i]=inf;
}
}
}
int x,y,z,w,q;
while(m--){//读入边 
cin>>x>>y>>z>>w>>q;
e[x][y]=w,t[x][y]=q;
if(!z)e[y][x]=w,t[y][x]=q;
}
cin>>s>>v;//起点，终点 
for(int i=0;i<n;i++){
d[i]=e[s][i],p[i]=t[s][i];
}
memset(pre,-1,sizeof(pre));
dijkstra(n,s);
flag=0;
swap(d,p);swap(e,t);
memset(vis,0,sizeof(vis));
memset(num,0,sizeof(num));
memset(pre2,-1,sizeof(pre2));
dijkstra(n,s);
int cn=0,cn2=0,road[N],road2[N],k=v,l=v;
while(k!=-1){
road[cn++]=k;
k=pre[k];
}
while(l!=-1){
road2[cn2++]=l;
l=pre2[l];
}
int mit=d[v];//最短时间
int mid=p[v];
if(judge(road,cn,road2,cn2)){
cout<<"Time = "<<mit<<"; Distance = "<<mid<<": "<<s;
for(int i=cn-1;i>=0;i--){
cout<<" => "<<road[i];
}
}else{
cout<<"Time = "<<mit<<": "<<s;
for(int i=cn-1;i>=0;i--){
cout<<" => "<<road[i];
}
cout<<endl;
cout<<"Distance = "<<mid<<": "<<s;
for(int i=cn2-1;i>=0;i--){
cout<<" => "<<road2[i];
}
}
return 0;
}