2019ICPC南京网络赛B题--Fire-Fighting Hero--spfa/dij最短路+超级源点

This is an era of team success, but also an era of heroes. Throughout the ages, there have been numerous examples of using the few to defeat the many. There are VVV (Numbers 111 to VVV) fire-fighting points in ACM city. These fire-fighting points have EEE roads to communicate with each other. Among them, there is a fire-fighting hero in the SSS fire-fighting point, and the fire-fighting team is distributed in K fire-fighting points. If a fire-fighting point needs to be put out, the fire-fighting hero or the fire-fighting team must arrive as soon as possible, that is, to choose the shortest route to arrive.

Today, our fire-fighting heroes want to challenge the fire-fighting team. The challenge is to: The maximum value of the shortest path for a fire-fighting hero to go to others fire-fighting points is compared with the maximum value of the shortest path for a fire-fighting team to go to others fire-fighting points from any point in their fire-fighting points. Because firefighting heroes are different and run faster, the maximum value of the shortest path they get should be discounted first, that is, multiplied by a coefficient of 1C\frac{1}{C}C1​, and then compared. The smaller one wins. Who is the real firefighter in this situation?

Who is the real firefighter in this situation?
Input

The first line contains a positive integer T(1≤T≤10)T (1\le T \le 10)T(1≤T≤10), which indicates that there are TTT cases of test data.

The format of each case of test data is as follows:

Line 111 contains five positive integers V(1≤V≤1000)V (1 \le V \le 1000)V(1≤V≤1000), E(V−1≤E≤V∗V2)E (V-1 \le E \le \frac{V*V}{2})E(V−1≤E≤2V∗V​), S(1≤S≤V)S (1 \le S \le V)S(1≤S≤V), K(1≤K≤V)K (1\le K \le V)K(1≤K≤V) and C(1≤C≤10)C (1\le C\le 10)C(1≤C≤10), the meanings are shown above.
Line 222 contains KKK positive integers, which in turn denotes the location number of the fire-fighting point where the fire-fighting team is located.

In the next EEE line, three positive integers i,j(1≤i,j≤V)i, j (1 \le i, j \le V)i,j(1≤i,j≤V) and L(1≤L≤10000)L (1 \le L \le 10000)L(1≤L≤10000) per line. Represents a path, i,ji, ji,j as the endpoint (fire-fighting point), LLL as the length of the path.
Output

Each case of test data outputs one line, which is a integer. That is, the maximum value of the shortest path of the winner (If the fire hero wins, the maximum value before the discount should be output). A draw is also a victory for fire-fighting hero.
样例输入

1
4 7 3 2 2
1 4
1 2 7
1 3 2
1 4 6 
2 1 1
2 4 1
3 2 1
3 4 3

样例输出

2

题意：有一个超人在位置S点，然后有k个灭火队，分布在位置a1,a2,ak上，然后现在问你，超人S到其他所有点救火，记录到某个点最短路的最大耗时为ans1，同时K个灭火队也救火，也记录到某个点最短路的最大耗时为ans2，然后如果ans1*C<=ans2说明超人赢了，输出ans1，不然输出ans2

题解：针对超人的最短路最大值，直接以S为源点跑最短路，针对消防队，因为有K个消防队，所以建立一个源点0连接这K个点，然后以0为源点跑最短路。

AC代码

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<queue>
#include<stack>
#include<string.h>
using namespace std;
const int N=200000;
struct Node{
	int v,w,next;
}edge[4*N];
int head[N],cnt;
void add_edge(int u,int v,int w)
{
	edge[cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	head[u]=cnt++;	
} 
bool vis[N];
int dis[N];
queue<int>q;
int n,m;
void spfa(int x)
{
	while(!q.empty())
	q.pop();
	memset(vis,0,sizeof(vis));
	for(int i=0;i<=n;i++)
	dis[i]=1e9;
	dis[x]=0;
	vis[x]=true;
	q.push(x);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=false;
		for(int i=head[u];i!=-1;i=edge[i].next)
		{

			int v=edge[i].v;
			int w=edge[i].w;
		//	cout<<"&"<<u<<" "<<v<<" "<<w<<endl;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				if(!vis[v])
				{
					vis[v]=true;
					q.push(v);
				}
			}
		}
	}
}
int pos[N]; 
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int S,K,C;
		scanf("%d%d%d%d%d",&n,&m,&S,&K,&C);
		for(int i=1;i<=K;i++)
		scanf("%d",&pos[i]);
		
		memset(head,-1,sizeof(head));
		cnt=0;
		for(int i=1;i<=m;i++)
		{
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			add_edge(x,y,z);
			add_edge(y,x,z);
		}
		spfa(S);
		int ans1=0;
		for(int i=1;i<=n;i++)
		ans1=max(dis[i],ans1);
		//建立超级源点0
		for(int i=1;i<=K;i++)
		add_edge(0,pos[i],0);
		spfa(0);
		int ans2=0;
		for(int i=0;i<=n;i++)
		ans2=max(dis[i],ans2);
		if(ans1<=ans2*C)
		printf("%d\n",ans1);
		else printf("%d\n",ans2);
	}
}