L3-007 天梯地图 (30 point(s))

104 阅读 0 评论 69 点赞

我是靠谱客的博主体贴纸飞机，最近开发中收集的这篇文章主要介绍L3-007 天梯地图 (30 point(s))，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在这里插入图片描述
两次spfa+两次dfs
通过邻接链表存边，求最短时间时相等时间求最短长度，直接存边的下标再进行判断

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 510 , M = N*N;
vector<pair<int,int>>lj1[N],lj2[N],temp;
vector<int>path1,path2;
int dist1[N],e[M],ne[M],w[M],t[M],h[N],idx=1;
bool st1[N],st2[N];
int s,d,n,m,dist2[N];
int q,z,c,sj,op,mintime=1e9,minlength=1e9;
int ts2=1e9;
int cddd=1e9;
inline void add(int a,int b,int c,int d){
e[idx]=b,ne[idx]=h[a],w[idx]=c,t[idx]=d,h[a]=idx++;
}
int cdd=1e9;
void spfa(int u){
queue<int>p1,p2;
if(u==1){
p1.push(s);st1[s]=1;
memset(st1,0,sizeof st1);
memset(dist1,0x3f,sizeof dist1);
dist1[s]=0;
while(!p1.empty()){
int x=p1.front();
p1.pop();
st1[x]=0;
for(int i=h[x];i!=-1;i=ne[i]){
int j=e[i];
if(dist1[j]>dist1[x]+w[i]){
dist1[j]=dist1[x]+w[i];
lj1[j].clear();
lj1[j].push_back({x,w[i]});
if(!st1[j])p1.push(j),st1[j]=1;
}else if(dist1[j]==dist1[x]+w[i]){
lj1[j].push_back({x,w[i]});
}
}
}}
else if(u==2){
p2.push(s);st2[s]=1;
memset(dist2,0x3f,sizeof dist2);
memset(st2,0,sizeof st2);
dist2[s]=0;
while(!p2.empty()){
int x=p2.front();
p2.pop();
st2[x]=0;
for(int i=h[x];i!=-1;i=ne[i]){
int j=e[i];
if(dist2[j]>dist2[x]+t[i]){
dist2[j]=dist2[x]+t[i];
lj2[j].clear();
lj2[j].push_back({x,i});
if(!st2[j])p2.push(j),st2[j]=1;
}else if(dist2[j]==dist2[x]+t[i]){
lj2[j].push_back({x,i});
}
}
}
}
}
void dfs1(int a,int b){
//time
temp.push_back({a,b});
if(a==s){
int time=0,tt=0;
for(int i=0;i<temp.size();i++)time+=t[temp[i].second];
if(time<mintime){
path1.clear();
for(int i=temp.size()-1;i>=0;i--){
path1.push_back(temp[i].first);
}
for(int i=0;i<temp.size();i++)tt+=w[temp[i].second];
cddd=tt;
mintime=time;
}else if(time==mintime){
for(int i=0;i<temp.size();i++)tt+=w[temp[i].second];
if(tt<cddd){
path1.clear();
cddd=tt;
for(int i=temp.size()-1;i>=0;i--){
path1.push_back(temp[i].first);
}
}
}
temp.pop_back();
return ;
}
for(int i=0;i<lj2[a].size();i++)
dfs1(lj2[a][i].first,lj2[a][i].second);
temp.pop_back();
}
void dfs2(int a,int b){//length
temp.push_back({a,b});
if(a==s){
int cd=0;
for(int i=0;i<temp.size();i++)cd+=temp[i].second;
if(cd<minlength){
path2.clear();
for(int i=temp.size()-1;i>=0;i--){
path2.push_back(temp[i].first);
}
minlength=cd;
ts2=temp.size();
}else if(cd==minlength){
if(temp.size()<ts2)
{ path2.clear();
ts2=temp.size();
for(int i=temp.size()-1;i>=0;i--){
path2.push_back(temp[i].first);
}
}
}
temp.pop_back();
return ;
}
for(int i=0;i<lj1[a].size();i++)
dfs2(lj1[a][i].first,lj1[a][i].second);
temp.pop_back();
}
int main(){
memset(h,-1,sizeof h);
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d %d %d %d %d",&q,&z,&op,&c,&sj);
add(q,z,c,sj);
if(!op)add(z,q,c,sj);
}
scanf("%d %d",&s,&d);
spfa(1);
spfa(2);
dfs1(d,0);
temp.clear();
dfs2(d,0);
if(path1==path2){
//
Time = T; Distance = D: 起点 => 节点1 => ... => 终点
cout<<"Time = "<<mintime<<"; "<<"Distance = "<<minlength<<":";
for(int i=0;i<path1.size();i++){
cout<<" "<<path1[i];
if(i!=path1.size()-1)cout<<" =>";
}
}
else {
cout<<"Time = "<<mintime<<":";
for(int i=0;i<path1.size();i++){
cout<<" "<<path1[i];
if(i!=path1.size()-1)cout<<" =>";
}
puts("");
cout<<"Distance = "<<minlength<<":";
for(int i=0;i<path2.size();i++){
cout<<" "<<path2[i];
if(i!=path2.size()-1)cout<<" =>";
}
}
}