[10.26_P2] 最短路 (单源最短路应用)

单源最短路问题拓展

Description

给你一张图，图上有 n 个点，m 条边，要你找到两个点，使其最短路恰好包含给定的 k 个点。输出这条最短路的长度，输入保证有解。

输入格式

第一行两个数 n , m。表示有 n 个点，m 条边。

接下来 m 行每行三个数 xi, yi, vi, 表示有一条长度为vi的双向路径连接对应的两个点。

接下来一个数 k。

接下来一行 k 个数，表示一定要包含的点。

输出格式

一个数，符合要求的最短路长度。

样例输入

样例一

6 6

1 2 2

2 6 2

1 3 1

3 4 1

4 5 1

5 6 1

3

5 1 3

样例二

6 6

1 2 2

2 6 2

1 3 1

3 4 1

4 5 1

5 6 1

2

1 6

样例输出

样例一

3

样例二

4

数据范围：

对于30%的数据，1<=N<=10,1<=M<=20

对于60%的数据，1<=N<=500,1<=M<=1000。

对于100%的数据，1<=N<=100000,1<=M<=300000,1<=vi<=10000，1<=K<=N,保证有解。

题解

我们可以很容易地看出，对于满足要求的这条最短路的两个端点一定是属于要包含的点。因为如果不是，我们可以删掉这个端点，得到的解一定会更优。所以，如果我们找到了这两个端点，就可以很容易地求出答案。

那么我们如何找到这两个端点呢？根据题意，所有需要包含的点均在这条路径上，端点一定是其他点能到达的最远的点。所以我们任取一个包含的点，做一次单源最短路，找到离他最远的那个需要包含的点，这一定是一个端点。

我们再以这个端点做一次单源最短路，即可找到另一个端点。同时，另一个端点到此端点的距离已经求出了。所以一共只用做两遍单源最短路即可得出最后的答案。

代码

#include <cstdio>

#include <iostream>

#include <queue>

using namespace std;

#define adde(u,v,w) {e[cnt] = (edge){v,w,head[u]};head[u] = &e[cnt++];}

const int maxn = 1e5 + 5, maxm = 3e5 + 5;

const long long inf = 1e12;

int n,m,k;

long long dis[maxn];

int cnt;

int can[maxn];

bool inq[maxn];

queue<int>q;

struct edge {

	int v;

	long long w;

	edge *next;

}e[maxm * 2], *head[maxn];

int spfa(int s) {

	while(!q.empty())q.pop();

	for(int i = 1;i <= n;i++)dis[i] = inf,inq[i] = 0;

	dis[s] = 0;

	q.push(s);

	inq[s] = 1;

	while(!q.empty()) {

		int u = q.front();q.pop();inq[u] = 0;

		for(edge *k = head[u];k;k = k->next) {

			if(dis[u] + k->w < dis[k->v]) {

				dis[k->v] = dis[u] + k->w;

				if(!inq[k->v]) {

					inq[k->v] = 1;q.push(k->v);

				}

			}

		}

	}

	int ans = 0,t = s;

	for(int i = 0;i < k;i++)if(dis[can[i]] > ans) ans = dis[can[i]], t = can[i];

	return t;

}

int main() {

	scanf("%d%d",&n,&m);

	for(int i = 0;i < m;i++) {

		int u,v,w;

		scanf("%d%d%d",&u,&v,&w);

		adde(u,v,w);adde(v,u,w);

	}

	scanf("%d",&k);

	for(int i = 0;i < k;i++) {

		int x;scanf("%d",&x);can[i] = x;

	}

	int t = spfa(can[0]);

	t = spfa(t);

	printf("%lld",dis[t]);

	return 0;

}

巴特西