当前位置:网站首页>(2022牛客多校三)J-Journey(dijkstra)
(2022牛客多校三)J-Journey(dijkstra)
2022-08-08 23:06:00 【AC__dream】
题目:
样例输入:
4
3 4 0 0
0 0 4 3
2 1 0 0
2 0 0 1
4 2 4 1
样例输出:
1
题意:给定一个城市有若干个十字路口,右转需要不需要等红灯,直行、左转和掉头都需要等活动,要求从起点到终点最少要等多少次红灯。
分析:这道题我们可以把每条带方向的边看成一个点,注意一条边的两个方向看成是两个不同的点,处理好这些东西之后我们就可以用dijkstra跑一个最短路就可以了
重要的是怎么建图,对于一个边如果之前没有记录过我们可以直接把其看成一个点,但是我们怎么知道当前点到其他点之间的边是权值为1还是为0,这个就需要画图思考一下,比如我们现在与t点相邻的一个路口为1号十字路口,那么假如(t,1)是t路口的第一个边,那么我们可以找出来(1,t)是1号十字路口的第几条边,那么当前边的下一条边就是(t,1)右转的边,那么就将这两条边建一条权值为0的边即可,注意我们是把边抽象化为点,且建立的边是单向边,至于1号十字路口的其余三条边我们将(t,1)与其它三条边建立一条长度为1的边即可,就这样我们就完成建图,然后从起点跑一个最短路就可以求出答案。
细节见代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<unordered_map>
using namespace std;
typedef pair<int,int> PII;
#define int long long
unordered_map<long long,int>mp;
const int N=5e6+10,M=5e7+10;
int p[N][4];
int h[N],ne[M],e[M],w[M],idx;
int be,en,d[N];
bool vis[N];
void add(int x,int y,int z)
{
e[idx]=y;
w[idx]=z;
ne[idx]=h[x];
h[x]=idx++;
}
int dijkstra(int x)
{
memset(d,0x3f,sizeof(d));
d[x]=0;
priority_queue<PII,vector<PII>,greater<PII> >q;
q.push({0,x});
while(!q.empty())
{
int begin=q.top().second;
q.pop();
if(vis[begin]) continue;
vis[begin]=true;
for(int i=h[begin];i!=-1;i=ne[i])
{
int j=e[i];
if(d[j]>d[begin]+w[i])
{
d[j]=d[begin]+w[i];
q.push({d[j],j});
}
}
}
if(d[en]==0x3f3f3f3f3f3f3f3f) return -1;
return d[en];
}
signed main()
{
int n;
cin>>n;
int tt=0;
for(int i=1;i<=n;i++)
scanf("%lld%lld%lld%lld",&p[i][0],&p[i][1],&p[i][2],&p[i][3]);
for(int i=1;i<=4*n;i++) h[i]=-1;//注意这里的点的个数不是n,我们把每条边抽象为一个点
for(int i=1;i<=n;i++)
{
for(int j=0;j<4;j++)
{
int t=p[i][j];
if(t)
{
if(!mp[1ll*i*1e9+t]) mp[1ll*i*1e9+t]=++tt;
int k=0;
for(;k<4;k++)
if(p[t][k]==i) break;
k=(k+1)%4;
if(!mp[t*1e9+p[t][k]]) mp[t*1e9+p[t][k]]=++tt;
add(mp[i*1e9+t],mp[t*1e9+p[t][k]],0);
for(int l=1;l<4;l++)
{
k=(k+1)%4;
if(!mp[t*1e9+p[t][k]]) mp[t*1e9+p[t][k]]=++tt;
add(mp[i*1e9+t],mp[t*1e9+p[t][k]],1);
}
}
}
}
int a,b,c,d;
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
be=mp[a*1e9+b];
en=mp[c*1e9+d];
cout<<dijkstra(be);
return 0;
}
边栏推荐
- Kubernetes资源编排系列之四: CRD+Operator篇
- 如何使用 Eolink 实现 API 文档自动生成
- WeChat small program "decompiled" combat "behind to unpack the eggs
- WeChat applet wx:for loop output example
- 请问:支付宝上买基金安全吗
- wps a列不见了怎么办?wps a列不见了的解决方法
- 微信小程序项目--订单
- 全国各省市区行政代码 城市代码.txt
- Virtual router redundancy protocol VRRP - double-machine hot backup
- Introduction to Qt (4) - Continuous playback of pictures (the use of two timers)
猜你喜欢
wps备份与恢复在哪里?
CTF攻防世界
[Bug solution] ValueError: Object arrays cannot be loaded when allow_pickle=False
【CUDA】version switch freely
Analysis of WLAN - Wireless Local Area Network
套接字(Socket)
ArcPy elements batch to dwg
A preliminary study on the use of ndk and JNI
wps表格下拉选项怎么添加?wps表格下拉选项的添加方法
让IPv6强大的关键——NDP邻居发现协议
随机推荐
三国战绩物品序号.txt
word文档标题怎么自动编号?
Application Layer Protocol - RADIUS
Python object-oriented
wps a3格式怎么转换成a4?wps a3格式转换成a4的方法
DHCP的防御机制——DHCP Snooping(DHCP监听)
PMP考点有哪些啊?
JS中的预编译(AO、GO详解)
JSDay1-合并两个有序数组
DHCP's defense mechanism - DHCP Snooping (DHCP snooping)
请问:支付宝上买基金安全吗
人人熟知的IPV6竟然还有这么多细节
Porting ucos2 code from stm32 to GD32
ALIPAY WEB log in rsa encryption analysis record
浅析WLAN——无线局域网
CTFSHOW_WEB入门web213
JS中数组扁平化的几种方法
全国各省市区行政代码 城市代码.txt
用模态框 实现 注册 登陆
微信小程序项目--订单