最短路

[GZOI2019]旅行者

Posted by Dispwnl on April 21, 2019

题目

题解

有一道处理思路差不多的题

先处理出来感兴趣城市到其他点的最短距离以及是从哪个感兴趣城市转移过来的，在反着跑一遍用其他点更新感兴趣城市

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<queue>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=5e5+5;
struct p{
	int x,y,d;
}c[MAX],C[MAX];
struct q{
	int id;
	LL x;
	q(int ID=0,LL X=0) {id=ID,x=X;}
	bool operator< (const q &a)
	const{
		return x>a.x;
	}
};
int n,m,k,T,num,num1;
LL ans;
int col[MAX],h[MAX],H[MAX],t[MAX];
LL d[MAX],D[MAX];
bool use[MAX];
priority_queue<q> qu; 
int read()
{
	int x(0);
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
void Dijkstra()
{
	memset(d,127,sizeof(d));
	memset(use,0,sizeof(use));
	for(int i=1;i<=k;++i)
	  qu.push(q(t[i])),d[t[i]]=0,col[t[i]]=t[i];
	while(!qu.empty())
	{
		q tt=qu.top();
		qu.pop();
		if(use[tt.id]) continue;
		use[tt.id]=1;
		for(int i=h[tt.id],y;i;i=c[i].x)
		  if(!use[y=c[i].y]&&d[y]>tt.x+c[i].d) d[y]=tt.x+c[i].d,col[y]=col[tt.id],qu.push(q(y,d[y]));
	}
}
void Dijkstra_(int *h=H,p *c=C)
{
	memset(D,127,sizeof(D));
	memset(use,0,sizeof(use));
	for(int i=1;i<=k;++i)
	  qu.push(q(t[i])),D[t[i]]=0;
	while(!qu.empty())
	{
		q tt=qu.top();
		qu.pop();
		if(use[tt.id]) continue;
		use[tt.id]=1;
		for(int i=h[tt.id],y;i;i=c[i].x)
		  {
		  	if(col[tt.id]!=col[y=c[i].y]) ans=min(ans,D[tt.id]+d[y]+c[i].d);
		  	if(!use[y]&&D[y]>tt.x+c[i].d) D[y]=tt.x+c[i].d,qu.push(q(y,D[y]));
		  }
	}
}
void add(int x,int y,int d) {c[++num]=(p){h[x],y,d},h[x]=num;}
void Add(int x,int y,int d) {C[++num1]=(p){H[x],y,d},H[x]=num1;}
int main()
{
	T=read();
	while(T--)
	{
		n=read(),m=read(),k=read(),num=num1=0,ans=1e18;
		memset(h,0,sizeof(h));
		memset(H,0,sizeof(H));
		memset(col,0,sizeof(col));
		for(int i=1,x,y,d;i<=m;++i)
		  x=read(),y=read(),d=read(),add(x,y,d),Add(y,x,d);
		for(int i=1;i<=k;++i)
		  t[i]=read();
		Dijkstra(),Dijkstra_(),printf("%lld\n",ans);
	}
	return 0;
}
FRIENDS