20191030 練習：多源最短路

第二道黑題祭~~~

P5304 [GXOI/GZOI2019]旅行者

（P5304 [GXOI/GZOI2019]旅行者）

題目描述

J J J 國有 n n n 座城市，這些城市之間通過 m m m 條單向道路相連，已知每條道路的長度。

一次，居住在 J J J 國的 R a i n b o w Rainbow Rainbow 邀請 V a n i Vani Vani 來作客。不過，作為一名資深的旅行者， V a n i Vani Vani 隻對 J J J 國的 k k k 座曆史悠久、自然風景獨特的城市感興趣。

為了提升旅行的體驗， V a n i Vani Vani 想要知道他感興趣的城市之間「兩兩最短路」的最小值（即在他感興趣的城市中，最近的一對的最短距離）。

也許下面的劇情你已經猜到了—— V a n i Vani Vani 這幾天還要忙着去其他地方遊山玩水，就請你幫他解決這個問題吧。

輸入格式

每個測試點包含多組資料，第一行是一個整數 T T T，表示資料組數。注意各組資料之間是互相獨立的。

對于每組資料，第一行包含三個正整數 n , m , k n,m,k n,m,k 表示 J 國的 nn 座城市（從 1 ∼ n 1 \sim n 1∼n 編号）， m m m 條道路， V a n i Vani Vani 感興趣的城市的個數 k k k。

接下來 m m m 行，每行包括 3 3 3 個正整數 x , y , z x,y,z x,y,z，表示從第 x x x 号城市到第 y y y 号城市有一條長度為 z z z 的單向道路。注意 x , y x,y x,y 可能相等，一對 x , y x,y x,y 也可能重複出現。

接下來一行包括 k k k 個正整數，表示 V a n i Vani Vani 感興趣的城市的編号。

輸出格式

輸出檔案應包含 T T T 行，對于每組資料，輸出一個整數表示 k k k 座城市之間兩兩最短路的最小值。

輸入輸出樣例

輸入

2

6 7 3

1 5 3

2 3 5

1 4 3

5 3 2

4 6 5

4 3 7

5 6 4

1 3 6

7 7 4

5 3 10

6 2 7

1 2 6

5 4 2

4 3 4

1 7 3

7 2 4

1 2 5 3

輸出

5

6

說明/提示

樣例解釋

對于第一組資料， 1 1 1 到 3 3 3 最短路為 5 5 5； 1 1 1 到 6 6 6 最短路為 7 7 7； 3 , 6 3,6 3,6 無法到達，是以最近的兩點為 1 , 3 1,3 1,3，最近的距離為 5 5 5。

對于第二組資料， 1 1 1 到 2 2 2 最短路為 6 6 6； 5 5 5 到 3 3 3 最短路為 6 6 6；其餘的點均無法互相達，是以最近的兩點為 1 , 2 1,2 1,2 和 5 , 3 5,3 5,3，最近的距離為 6 6 6。

資料範圍

2 ≤ k ≤ n , 1 ≤ x , y ≤ n , 1 ≤ z ≤ 2 × 1 0 9 , T ≤ 52 ≤ k ≤ n , 1 ≤ x , y ≤ n , 1 ≤ z ≤ 2 × 1 0 9 , T ≤ 5 。 2 \le k \le n,1 \le x,y \le n,1 \le z \le 2 \times 10^9,T ≤52≤k≤n,1≤x,y≤n,1≤z≤2×10^9 ,T≤5。 2≤k≤n,1≤x,y≤n,1≤z≤2×109,T≤52≤k≤n,1≤x,y≤n,1≤z≤2×109,T≤5。

測試點編号 n n n 的規模 m m m 的規模 約定

1 ≤ 1 , 000 ≤ 5 , 000 \le 1,000 \le 5,000 ≤1,000≤5,000 無

2 ≤ 1 , 000 ≤ 5 , 000 \le 1,000 \le 5,000 ≤1,000≤5,000 無

3 ≤ 100 , 000 ≤ 500 , 000 \le 100,000 \le 500,000 ≤100,000≤500,000 保證資料為有向無環圖

4 ≤ 100 , 000 ≤ 500 , 000 \le 100,000 \le 500,000 ≤100,000≤500,000 保證資料為有向無環圖

5 ≤ 100 , 000 ≤ 500 , 000 \le 100,000 \le 500,000 ≤100,000≤500,000 保證資料為有向無環圖

6 ≤ 100 , 000 ≤ 500 , 000 \le 100,000 \le 500,000 ≤100,000≤500,000 無

7 ≤ 100 , 000 ≤ 500 , 000 \le 100,000 \le 500,000 ≤100,000≤500,000 無

8 ≤ 100 , 000 ≤ 500 , 000 \le 100,000 \le 500,000 ≤100,000≤500,000 無

9 ≤ 100 , 000 ≤ 500 , 000 \le 100,000 \le 500,000 ≤100,000≤500,000 無

10 ≤ 100 , 000 ≤ 500 , 000 \le 100,000 \le 500,000 ≤100,000≤500,000 無

思路：

類似20191029 csp-s模拟T3（多源最短路）

但是為了避免對頂的情況，要在正反兩個圖上各跑一次 D i j k s t r a Dijkstra Dijkstra。

代碼：

#include<bits/stdc++.h>
using namespace std;
#define in Read()

long long in{
	long long s=0,f=1;char x;
	for(x=getchar();!isdigit(x);x=getchar())    if(x=='-')  f=-1;
	for( ;isdigit(x);x=getchar())   s=(s<<1)+(s<<3)+(x&15);
	return s*f;
}

const long long A=1e6+5;
long long t;
long long n,m,k;
long long u,v,w;
long long xx[A],yy[A],ww[A];
long long head[A],tot=1;
struct Road{
	long long nex,to,w;
}road[A];
inline void ljb(long long x,long long y,long long w){road[++tot]={head[x],y,w};head[x]=tot;}
long long p[A];
long long res=1e18;
long long s[A][2],f[A][2];
bool ex[A][2];

inline void djk(long long d){
	for(long long i=1;i<=n;i++)   s[i][d]=1e18,ex[i][d]=0;
	priority_queue <pair<long long,long long> > q;
	for(long long i=1;i<=k;i++){
		s[p[i]][d]=0,f[p[i]][d]=p[i];
		q.push(make_pair(0,p[i]));
	}
	while(!q.empty()){
		long long x=q.top().second;q.pop();
		if(ex[x][d])    continue;
		ex[x][d]=1;
		for(long long y=head[x];y;y=road[y].nex){
			long long z=road[y].to,w=road[y].w;
			if(s[z][d]>s[x][d]+w){
				s[z][d]=s[x][d]+w,f[z][d]=f[x][d];
				q.push(make_pair(-s[z][d],z));
			}
		}
	}
}

inline void clean(){
	for(long long i=1;i<=n;i++)head[i]=0;
	tot=0;
}

signed main(){
	t=in;
	while(t--){
  		res=1e18;
		n=in,m=in,k=in;
		clean();
		for(long long i=1;i<=m;i++){
			u=in,v=in,w=in;
			xx[i]=u,yy[i]=v,ww[i]=w;
			ljb(u,v,w);
		}
		for(long long i=1;i<=k;i++)
			p[i]=in;
		djk(0);
		clean();
		for(long long i=1;i<=m;i++)
			ljb(yy[i],xx[i],ww[i]);
		djk(1);
		for(long long i=1;i<=m;i++){
			long long x=xx[i],y=yy[i],w=ww[i];
			if(f[x][0]&&f[y][1]&&f[x][0]!=f[y][1])
					res=min(res,s[x][0]+s[y][1]+w);
		}
		printf("%lld\n",res);
	}
	return 0;
}