1111 Online Map (30 分)【难度: 一般 / 知识点: Dijkstra最短路】
2023-09-11 14:15:52 时间
https://pintia.cn/problem-sets/994805342720868352/problems/994805358663417856
很传统的最短路,不过要跑两次,其实分开来的话每一问都是比较常规的题目。
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int L[N][N],T[N][N],vis[N],dist1[N],dist2[N];
int n,m,st,ed;
vector<int>ans1,ans2,path;
int max_time=1e9,min_cnt=1e9;
void Dijkstra(int g[N][N],int dist[N])
{
for(int i=0;i<n;i++) dist[i]=0x3f3f3f3f;
dist[st]=0;
memset(vis,0,sizeof vis);
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=0;j<n;j++)
if(!vis[j]&&(t==-1 || dist[j]<dist[t])) t=j;
vis[t]=1;
for(int j=0;j<n;j++) dist[j]=min(dist[j],dist[t]+g[t][j]);
}
}
void dfs1(int u,int fa,int sum)
{
if(u==ed)
{
if(sum<max_time) max_time=sum,ans1=path;
return;
}
for(int i=0;i<n;i++)
{
if(i==fa) continue;
if(dist1[i]==dist1[u]+L[u][i])//是对短路上的点
{
path.push_back(u);
dfs1(i,u,sum+T[u][i]);
path.pop_back();
}
}
}
void dfs2(int u,int fa,int sum)
{
if(u==ed)
{
if(sum<min_cnt) ans2=path,min_cnt=sum;
return;
}
for(int i=0;i<n;i++)
{
if(i==fa) continue;
if(dist2[i]==dist2[u]+T[u][i])
{
path.push_back(u);
dfs2(i,u,sum+1);
path.pop_back();
}
}
}
int main(void)
{
memset(L,0x3f,sizeof L);
memset(T,0x3f,sizeof T);
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a,b,op,l,t; cin>>a>>b>>op>>l>>t;
if(op)
{
L[a][b]=min(L[a][b],l);
T[a][b]=min(T[a][b],t);
}
else
{
L[a][b]=min(L[a][b],l);
L[b][a]=min(L[b][a],l);
T[a][b]=min(T[a][b],t);
T[b][a]=min(T[b][a],t);
}
}
cin>>st>>ed;
Dijkstra(L,dist1);
Dijkstra(T,dist2);
dfs1(st,-1,0);
dfs2(st,-1,0);
if(ans1!=ans2)
{
printf("Distance = %d: ",dist1[ed]);
for(int i=0;i<ans1.size();i++) cout<<ans1[i]<<" -> ";
cout<<ed<<endl;
printf("Time = %d: ",dist2[ed]);
for(int i=0;i<ans2.size();i++) cout<<ans2[i]<<" -> ";
cout<<ed<<endl;
}else
{
printf("Distance = %d; Time = %d: ",dist1[ed],dist2[ed]);
for(int i=0;i<ans1.size();i++) cout<<ans1[i]<<" -> ";
cout<<ed<<endl;
}
return 0;
}
相关文章
- 微信小程序 - 滑动显示地点信息(map)
- Google Earth Engine(GEE)——利用map遍历实现影像的逐年筛选
- Java面试题答案解析: 基础考核-拆箱装箱, 数据类型, MAP
- 133Echarts - 路径图(Bus Lines of Beijing - Baidu Map)
- 后台开发:核心技术与应用实践3.4.2 map的查增删
- javascript实现java的map对象,js实现new map()
- 循环遍历Map的4中方法
- jquery---调用静态方法-each--map-数组与伪数组的差别
- map比起unordered_map的优势主要有(hashmap就是unordered_map)
- nyoj 1112 求次数 (map)
- 原生js源码之Array数组map方法
- 【bzoj5206】[Jsoi2017]原力 根号分治+STL-map