$$\color{Purple}{kuangbin题解目录}$$
描述
Nya 图是一种分层的无向图。
图中共有 $N$ 个节点,每个节点都处于某一层当中。
层与层之间存在阶梯。
利用阶梯可以从任意一层的任意一个节点移动至其相邻层(上一层或下一层)的任意一个节点。
每次利用阶梯进行移动都需要花费固定的成本 $C$。
此外,还有 $M$ 个点对之间存在额外边。
如果点 $u$ 和点 $v$ 之间存在额外边,则可以通过额外边在点 $u$ 和点 $v$ 之间进行双向移动。
每次利用额外边进行移动都需要花费一定的成本,不同额外边的花费可能不同。
请你计算从点 $1$ 移动至点 $N$ 所需花费的最低成本。
输入格式
第一行包含一个整数 $T$,表示共有 $T$ 组测试数据。
每组数据第一行包含三个整数 $N,M,C$。
第二行包含 $N$ 个整数 $l_i$,表示每个点所在的具体层数。
接下来 $M$ 行,每行包含三个整数 $u,v,w$,表示点 $u$ 和点 $v$ 之间存在一条额外边,成本为 $w$。
输出格式
每组数据输出一行答案,具体格式为 Case #x: y
,其中 $x$ 为组别编号(从 $1$ 开始),$y$ 为所需花费的最低成本。如果无法到达点 $N$,则为 $\-1$。
数据范围
$1 \\le T \\le 20$,
$0 \\le N,M \\le 10^5$,
$1 \\le C \\le 10^3$,
$1 \\le l_i \\le N$,
$1 \\le u,v \\le N$,
$u \\neq v$,
$1 \\le w \\le 10^4$。
输入样例:
2
3 3 3
1 3 2
1 2 1
2 3 1
1 3 3
3 3 3
1 3 2
1 2 2
2 3 2
1 3 4
输出样例:
Case #1: 2
Case #2: 3
思路
- 该题中每一个点都有对应的层数,若将每相邻两层之间的所有点建立边(包含同一层)以及本身的$m$条双向边,必然会
爆掉空间
(最坏情况下,假设上层有$5\times 10^4$个点,下层也有$5\times 10^4$个点,需要建立的边数大约为$(5\times 10^4)^2+2\times 10^5=2.5\times 10^9+2\times 10^5$);- 故该题每相邻两层之间需要设置
虚拟源点
,当前点到本层的虚拟源点
距离为$0$,上一层或下一层的虚拟源点
到当前点
距离为$C$,此时只需建立大约$3\times 10^5+2\times 10^5=5\times 10^5$条边即可解决空间爆掉
的问题.- 故先将
当前点
转移到当前层的虚拟源点
上,再进行虚拟源点
到其他点
的移动;- 设有$n$个点,$n$个点的数据范围为$1\sim n$,虚拟源点的数据范围为$\color{Red}{n+1+1\sim 2\times n+1}$,由于考虑到第一层向下走时,若虚拟源点的数据范围为$n+1\sim 2\times n$,此时会在点$1$到点$n$之间建立边权为$C$的点(
虽然这题并没有卡这个虚拟源点的数据范围)- 其
虚拟源点建边
的代码如下,其中$level$表示点$i$的层数:
add(i,level+n+1,0);//i到同层的虚拟源点,距离为0
add(level+n+1-1,i,C);//下一层虚拟源点到i,距离为C
add(level+n+1+1,i,C);//上一层虚拟源点到i,距离为C
代码
// Problem: Nya图最短路
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4254/
// Memory Limit: 64 MB
// Time Limit: 5000 ms
// Date: 2023-01-28 15:16:22
//
// 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 200010//此处后一半建立每一层的虚拟源点
#define MAXM 500010//m条双向边+3*n个虚拟源点单向边
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int inf=0x3f3f3f3f;
int t,n,m,C;
int head[MAXN],ed[MAXM],nex[MAXM],val[MAXM],idx;
int dist[MAXN],vis[MAXN];
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));
dist[start]=0;
priority_queue<PII,vector<PII>,greater<PII> > q;
q.push({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});
}
}
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
int Cas=1;
scanf("%d",&t);
while(t--)
{
memset(head,-1,sizeof(head));
idx=0;
scanf("%d %d %d",&n,&m,&C);
for(int i=1;i<=n;i++)
{
int level;
scanf("%d",&level);
//1~n--->虚拟源点: n+1代表第0层的虚拟源点(若用n+1~2*n此时有可能在1和n之间(由于1对应向下的虚拟源点为n+1-1=n)建立长度为C的边) n+2~2*n+1
add(i,level+n+1,0);//i到同层的虚拟源点,距离为0
add(level+n+1-1,i,C);//下一层虚拟源点到i,距离为C
add(level+n+1+1,i,C);//上一层虚拟源点到i,距离为C
}
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
Dijkstra(1);
if(dist[n]==inf)
dist[n]=-1;
printf("Case #%d: %d\n",Cas++,dist[n]);
}
return 0;
}