$$\color{Purple}{kuangbin题解目录}$$
描述
某城市共有 $n$ 个电车站点,编号 $1 \\sim n$。
现在,我们要乘坐电车从 $A$ 站点前往 $B$ 站点。
电车在第 $i$ 个站点可以驶往 $k_i$ 个其他站点,其中一个站点为默认驶往站点,如果电车驶往非默认站点,则需要进行一次变道。
我们希望从 $A$ 到 $B$ 的过程中,电车变道的次数尽可能少。
请问,最少需要进行多少次变道。
输入格式
第一行包含三个整数 $n,A,B$。
接下来 $n$ 行,其中第 $i$ 行首先包含一个整数 $k_i$,表示第 $i$ 个站点可以驶往的站点数量,然后包含 $k_i$ 个整数,表示每个可驶往的站点编号,其中第 $1$ 个给出的站点为默认驶往站点。
输出格式
一个整数,表示最少变道次数。
如果无法从 $A$ 到 $B$,则输出 $\-1$。
数据范围
$2 \\le N \\le 100$,
$1 \\le A,B \\le N$,
$0 \\le K_i \\le N-1$。
输入样例:
3 2 1
2 2 3
2 3 1
2 1 2
输出样例:
0
思路
- 给定
起点和终点
,以及每个点的默认站点
(边权设置为$\color{Red}0$,表示不变道)和非默认站点
(边权设置为$\color{Pink}1$,表示需要变道$1$次才能到达),然后跑单源最短路
即可;- 由于数据范围
比较小
,可用floyd算法
解决.
代码
- $Dijkstra$(朴素版)
// Problem: 电车
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4252/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-28 14:33:36
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 110
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int n,A,B;
int val[MAXN][MAXN];
int dist[MAXN],vis[MAXN];
void Dijkstra(int start)
{
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
dist[start]=0;
for(int i=1;i<n;i++)
{
int pos=-1;
for(int j=1;j<=n;j++)
if(vis[j]==0&&(pos==-1||dist[j]<dist[pos]))
pos=j;
vis[pos]=1;
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],dist[pos]+val[pos][j]);
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> n >> A >> B;
memset(val,0x3f,sizeof(val));
for(int i=1;i<=n;i++)
{
int k,pos;
cin >> k;
for(int j=1;j<=k;j++)
{
cin >> pos;
if(j==1)//不变道
val[i][pos]=0;
else val[i][pos]=1;//变道
}
}
Dijkstra(A);
if(dist[B]==inf)
cout << -1 << endl;
else cout << dist[B] << endl;
return 0;
}
- $Dijkstra$(堆优化版)
// Problem: 电车
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4252/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-28 14:33:36
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 110
#define MAXM 10010
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int inf=0x3f3f3f3f;
int n,A,B;
int dist[MAXN],vis[MAXN];
int head[MAXN],ed[MAXM],nex[MAXM],val[MAXM],idx;
void add(int a,int b,int c)
{
ed[idx]=b;
val[idx]=c;
nex[idx]=head[a];
head[a]=idx++;
}
void Dijkstra(int start)
{
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
priority_queue<PII,vector<PII>,greater<PII> > q;
dist[start]=0;
//q.push({0,start});
q.push(make_pair(0,start));
while(q.size()>0)
{
PII temp=q.top();
q.pop();
int temp_dis=temp.first,temp_pos=temp.second;
if(vis[temp_pos]==1)
continue;
vis[temp_pos]=1;
for(int i=head[temp_pos];i!=-1;i=nex[i])
{
int j=ed[i];
if(vis[j]==1)
continue;
if(dist[j]>temp_dis+val[i])
{
dist[j]=temp_dis+val[i];
//q.push({dist[j],j});
q.push(make_pair(dist[j],j));
}
}
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> n >> A >> B;
memset(head,-1,sizeof(head));
for(int i=1;i<=n;i++)
{
int k,pos;
cin >> k;
for(int j=1;j<=k;j++)
{
cin >> pos;
if(j==1)//不变道
add(i,pos,0);
else add(i,pos,1);//变道
}
}
Dijkstra(A);
if(dist[B]==inf)
cout << -1 << endl;
else cout << dist[B] << endl;
return 0;
}
- $floyd$
// Problem: 电车
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4252/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-28 14:33:36
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 110
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int n,A,B;
int val[MAXN][MAXN];
void floyd()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
val[i][j]=min(val[i][j],val[i][k]+val[k][j]);
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> n >> A >> B;
memset(val,0x3f,sizeof(val));
for(int i=1;i<=n;i++)
{
int k,pos;
cin >> k;
for(int j=1;j<=k;j++)
{
cin >> pos;
if(j==1)//不变道
val[i][pos]=0;
else val[i][pos]=1;//变道
}
}
floyd();
if(val[A][B]==inf)
cout << -1 << endl;
else cout << val[A][B] << endl;
return 0;
}