P7192 [COCI2007-2008#6] GEORGE 题解

题目简述

给定一张 $n$ 个点 $m$ 条边的无向图，从 $u_i \rightarrow v_i$ 需要用时 $w_i$ 分钟。有一位 T 先生从 $0$ 时刻按有 $g$ 个点的序列顺序移动，即 $v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_g$。还有一位卡车司机 Luka 从 $k$ 时刻开始从 $a$ 点出发，Luka 不能与 T 先生在同一时间走同一条路，问 Luka 从 $a$ 点到 $b$ 点的最短路。

题目分析

注意到 T 先生的移动顺序是一定的，所以我们可以先处理出每一个时刻 T 先生在哪一条边上。

接下来，我们考虑使用 Dijkstra 算法求最短路，设当前队首可以扩展的点为 $u$，从点 $a$ 到点 $u$ 所需的最短时间为 $dis_u$，与 $u$ 的连边为 $u \rightarrow v$，如果 T 先生在 $dis_u$ 时刻恰好走在 $u \rightarrow v$ 这条边上，我们可以让 Luka 等到 T 先生走开再走这条边，就是将边权增大在进行松弛。如果 T 先生没走的话直接松弛就好了。

最后答案是 $dis_b-k$，因为 Luka 是从 $k$ 时刻开始走的。

代码

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=1e3+10;
const int M=1e4+10;
int n,m,a,b,k,g,t[N],cnt,head[N],cnt2,vis1[N],E[N][N],dis[N],vis2[N][N]; 
pair<int,int> vis[M*1000];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
struct edge
{
	int to,next,value;
}e[M*2];
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
	    if(ch=='-')
		{
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
	    x=(x<<1)+(x<<3)+ch-48;
	    ch=getchar();
	}
	return x*f;
}
inline void write(int x)
{
    if(x<0)
	{
    	putchar('-');
		x=-x;
	}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
void addedge(int u,int v,int w)
{
	e[++cnt]={v,head[u],w};
	head[u]=cnt;
}
int main()
{
	n=read();
	m=read();
	a=read();
	b=read();
	k=read();
	g=read();
	for(int i=1;i<=g;i++)
	{
		t[i]=read();
	}
	for(int i=1;i<=m;i++)
	{
		int u=read();
		int v=read();
		int w=read();
		addedge(u,v,w);
		addedge(v,u,w);
		E[u][v]=E[v][u]=w;
	}
	for(int i=1;i<=g-1;i++)
	{
		for(int j=1;j<=E[t[i]][t[i+1]];j++)
		{
			vis[++cnt2]={t[i],t[i+1]};
		}
		vis2[t[i]][t[i+1]]=cnt2;
	}
	memset(dis,0x3f,sizeof dis);
	q.push({k,a});
	dis[a]=k;
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis1[u]) continue;
		vis1[u]=1;
		for(int i=head[u];i;i=e[i].next)
		{
			int v=e[i].to,w=e[i].value; 
			if((vis[dis[u]].first==u&&vis[dis[u]].second==v)||(vis[dis[u]].first==v&&vis[dis[u]].second==u))
			{
				w+=vis2[vis[dis[u]].first][vis[dis[u]].second]-dis[u];
			}
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push({dis[v],v});
			}
		}
	}
	write(dis[b]-k);
	return 0;
}