题解

题目分析

这是一道基于图论和动态规划的题目，需要在有障碍物的图中寻找最优路径。

解题思路

1. 问题建模

• 构建有向图，节点数为 $m$，边数为 $e$
• 存在 $d$ 个障碍物，每个障碍物在特定时间段内阻塞某些节点
• 需要找到从节点 $1$ 到节点 $m$ 的最短路径

2. 图构建

• 使用邻接表存储图结构：head[N], ver[N<<1], nxt[N<<1], edge[N<<1]
• 每条边有权重，表示通过该边的时间
• 支持动态添加和删除边

3. 障碍物处理

• 定义障碍物结构：Node {p, l, r} 表示节点 $p$ 在时间段 $[l, r]$ 内被阻塞
• 使用 ban[] 数组标记当前被阻塞的节点
• 动态更新障碍物状态

4. 最短路径算法

• 使用 SPFA 算法计算最短路径
• 维护距离数组 dis[N] 和访问标记 vis[N]
• 考虑障碍物的时间约束

5. 动态规划

• 使用二维数组 g[i][j] 存储状态
• 状态转移基于图的最短路径
• 考虑时间因素和障碍物约束

6. 关键技巧

• 使用 INF = 1e9 作为无穷大值
• 队列优化：使用 queue<int> 实现 BFS
• 动态更新障碍物状态

时间复杂度

$O(VE)$，其中 $V$ 为节点数，$E$ 为边数。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=210;
const int INF=1e9;
int n,m,k,e,d,dis[N],f[N],g[N][N];
bool vis[N],ban[N];
int tot,head[N],ver[N<<1],nxt[N<<1],edge[N<<1];
struct Node
{
	int p,l,r;
}s[N];
void add_edge(int x,int y,int val)
{
	ver[++tot]=y; nxt[tot]=head[x];
	head[x]=tot; edge[tot]=val;
}
int calc(int l,int r)
{
	for(int i=1;i<=m;i++)
		vis[i]=ban[i]=false,dis[i]=INF;
	for(int i=1;i<=d;i++)
		if(!(s[i].l>r||s[i].r<l))
			ban[s[i].p]=true;
	queue<int> q;
	dis[1]=0; q.push(1); vis[1]=true;
	while(!q.empty())
	{
		int x=q.front(); q.pop(); vis[x]=false;
		for(int i=head[x];i;i=nxt[i])
		{
			int to=ver[i],val=edge[i];
			if(ban[to]) continue;
			if(dis[to]>dis[x]+val)
			{
				dis[to]=dis[x]+val;
				if(!vis[to]) q.push(to),vis[to]=true;
			}
		}
	}
	return dis[m];
}
signed main()
{
	cin>>n>>m>>k>>e;
	for(int i=1,x,y,val;i<=e;i++)
	{
		cin>>x>>y>>val;
		add_edge(x,y,val);
		add_edge(y,x,val); 
	}
	cin>>d;
	for(int i=1;i<=d;i++)
		cin>>s[i].p>>s[i].l>>s[i].r;
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			g[i][j]=calc(i,j);
	for(int i=1;i<=n;i++)
	{
		f[i]=g[1][i]*i;
		for(int j=0;j<i;j++)
			f[i]=min(f[i],f[j]+g[j+1][i]*(i-j)+k);
	}
	printf("%lld",f[n]);
	return 0;
}