题目描述

You are in charge of designing an advanced centralized traffic management system for smart cars. The goal is to use global information to instruct morning commuters, who must drive downtown from the suburbs, how best to get to the city center while avoiding traffic jams.

Unfortunately, since commuters know the city and are selfish, you cannot simply tell them to travel routes that take longer than normal (otherwise they will just ignore your directions). You can only convince them to change to different routes that are equally fast.

The city’s network of roads consists of intersections that are connected by bidirectional roads of various travel times. Each commuter starts at some intersection, which may vary from commuter to commuter. All commuters end their journeys at the same place, which is downtown at intersection 1. If two commuters attempt to start travelling along the same road in the same direction at the same time, there will be congestion; you must avoid this. However, it is fine if two commuters pass through the same intersection simultaneously or if they take the same road starting at different times.

Determine the maximum number of commuters who can drive downtown without congestion, subject to all commuters starting their journeys at exactly the same time and without any of them taking a suboptimal route.

In Figure C.1, cars are shown in their original locations. One car is already downtown. Of the cars at intersection 4, one can go along the dotted route through intersection 3, and another along the dashed route through intersection 2. But the remaining two cars cannot reach downtown while avoiding congestion. So a maximum of 3 cars can reach downtown with no congestion.

输入格式

The input consists of a single test case. The first line contains three integers $n, m,$ and $c$, where $n (1 \leq n \leq 25 000)$ is the number of intersections, $m (0 \leq m \leq 50 000)$ is the number of roads, and $c (0 \leq c \leq 1 000)$ is the number of commuters. Each of the next $m$ lines contains three integers $x_i, y_i$, and $t_i$ describing one road, where $x_i$ and $y_i (1 \leq x_i, y_i \leq n)$ are the distinct intersections the road connects, and $t_i (1 \leq t_i \leq 10 000)$ is the time it takes to travel along that road in either direction. You may assume that downtown is reachable from every intersection. The last line contains $c$ integers listing the starting intersections of the commuters.

输出格式

Display the maximum number of commuters who can reach downtown without congestion.

题目大意

【题目描述】

你负责设计一个先进的集中交通管理系统，以便为智能汽车提供服务。目标是利用全局信息指导早晨从郊区驾车前往市中心的通勤者，帮助他们避免交通拥堵。

不幸的是，由于通勤者了解城市且自私，你不能简单地让他们走比平时更慢的路线（否则他们会忽略你的指示）。你只能说服他们改变到同样快的不同路线。

城市的道路网络由连接双向道路的交叉口组成，各条道路的行驶时间不同。每个通勤者从某个交叉口出发，这些交叉口因人而异。所有通勤者的行程终点都是市中心的 1 号交叉口。如果两名通勤者同时在同一方向上行驶在同一条道路上，会造成拥堵；你必须避免这种情况。然而，如果两名通勤者同时经过同一个交叉口或者在不同时间使用同一条道路，这是允许的。

确定在所有通勤者同时开始旅程且没有任何人走次优路线的情况下，最多有多少通勤者可以在不拥堵的情况下开车到市中心。

【输入格式】

输入由一个单独的测试用例组成。第一行包含三个整数 $n, m, c$，其中 $n (1 \leq n \leq 25 000)$ 表示交叉口的数量，$m (0 \leq m \leq 50 000)$ 表示道路的数量，$c (0 \leq c \leq 1 000)$ 表示通勤者的数量。接下来的 $m$ 行中的每一行包含三个整数 $x_i, y_i, t_i$，描述了一条道路，其中 $x_i$ 和 $y_i (1 \leq x_i, y_i \leq n)$ 是道路连接的不同交叉口，$t_i (1 \leq t_i \leq 10 000)$ 是沿该道路行驶的时间。最后一行包含 $c$ 个整数，列出了通勤者的起始交叉口。

【输出格式】

显示最多有多少通勤者可以在不拥堵的情况下到达市中心。

翻译来自于：ChatGPT。

3 3 2
1 2 42
2 3 1
2 3 1
2 3

2

4 4 5
1 2 5
1 3 4
4 2 5
4 3 6
4 4 4 4 1

3