当前位置:网站首页>(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;
}
边栏推荐
猜你喜欢
随机推荐
三国战绩 风云再起 网络版 物品序号 和 基址列表
JSDay1-两数之和
stm32 利用 串口接收空闲中断 + dma 实现不定长度dma 接收
Firewall first contact
应用层协议——RADIUS
-Wl,--start-group ... -Wl,--end-group 用于解决几个库的循环依赖关系
PHP 正则给img的src添加域名
按键精灵 删除文件 命令
第二课:概率论
postman request+加密解密
Python object-oriented
【Bug解决】ValueError: Object arrays cannot be loaded when allow_pickle=False
用模态框 实现 注册 登陆
Hi3516 use wifi module
Kubernetes 资源编排系列之二: Helm 篇
考证必看 | PMP扫盲贴+PMP材料
腾讯技术支持实习二面——腾讯爸爸的临幸就是这么突然(offer到手)
[Bug solution] ValueError: Object arrays cannot be loaded when allow_pickle=False
【Verilog基础】关于芯片中信号串扰的理解
wps备份与恢复在哪里?