레이팅 미적용vertex=[auto=left,circle,fill=black!25,minimum size=20pt,inner sep=0pt]
Every year, your uncle organizes a get-together for the whole family. This year, he has decided that the best place for such a gathering is the picturesque city of Delft. However, your family is scattered across various different places in the Benelux, so everyone will have to take the train to Delft.
Train tickets are expensive these days, so your uncle has asked you to find the best deal to get everyone a valid ticket. Your family members have indicated that they do not like detours: they will only want to travel on one of the shortest routes from their starting station to Delft, so you'll have to take that into account when buying tickets.
After some quick research you find that there are two types of tickets: an individual ticket and a group ticket. Individual tickets are straightforward: the price of an individual ticket between two stations is equal to the shortest distance in kilometers between them. Group tickets are slightly more complicated. When you buy a group ticket, you indicate two stations and the names of any number of people. As long as all the people mentioned on the ticket are present, the group ticket allows them to travel between the two stations. This costs \(g\) euros per person, regardless of the distance between the stations. Due to strange regulations, you can only buy one group ticket in total, so you cannot divide the family into two or more groups. Note that a person can use both individual tickets and a group ticket on their journey.
What is the least you have to spend to get all of your family members valid tickets to Delft?
tikzpicture[scale=1] [vertex] (n1) at (0,0) \(1\); [vertex] (n2) at (3,0) \(2\); [vertex] (n3) at (6,0) \(3\); [vertex] (n4) at (9,0) \(4\); [vertex] (n5) at (3,-2) \(5\); [vertex] (n6) at (8,2) \(6\); [vertex] (n7) at (11,2) \(7\);
[line width=1.5pt] (n1) – (n2) node [midway,above] \(100\); [line width=1.5pt] (n2) – (n3) node [midway,above] \(100\); [red,dashed,line width=1.5pt,transform canvas=yshift=2pt] (n3) – (n4) node [midway,above] ; [line width=1.5pt,dashed,green,transform canvas=yshift=-2pt] (n3) – (n4) node [midway,above] ; [line width=1.5pt,dashed,blue,transform canvas=yshift=-3pt] (n3) – (n6) node [midway,above] ; [line width=1.5pt] (n3) – (n4) node [midway,above] \(10\); line width=1.5pt – (n6) node[xshift=-3pt] [midway,above] \(10\); line width=1.5pt – (n7) node [midway,above] \(5\); [line width=1.5pt,dashed,blue,transform canvas=yshift=-2pt] (n6) – (n7) node [midway,above] ; line width=5pt – (n5) node[xshift=-4pt,yshift=-1pt] [midway,left] \(80\); [line width=1.5pt,dashed,orange,transform canvas=yshift=3pt,xshift=3pt] (n1) – (n5) node [midway,above] ; line width=5pt – (n3) node[xshift=-3pt] [midway,left] \(30\);
tikzpicture
The input consists of:
- One line containing four integers: \(n\) (\(2 \le n \le 1000\)), the number of train stations, \(m\) (\(n-1 \le m \le 10^5\)), the number of connections between train stations, \(p\) (\(1 \le p \le 100\)), the number of family members, and \(g\) (\(1 \le g \le 10^6\)), the cost per person of a group ticket.
- The next line contains \(p\) integers \(v_i\) (\(1 \le v_i \le n\)), the \(i\)th of which indicates that family member \(i\) starts at station \(v_i\).
- Then follow \(m\) lines that each contain three integers \(a\), \(b\), and \(c\) (\({1 \le a,b \le n}\), \(a\neq b\), and \({1 \le c \le 10^6}\)), indicating that there is a bidirectional connection between stations \(a\) and \(b\) with a length of \(c\) kilometers.
There is at most one direct connection between any pair of distinct stations and every station can be reached from any other station.
The station of Delft is always numbered \(1\).
Output the total cost of the cheapest valid tickets so that every family member can travel from their starting station to Delft.
6 5 3 10
4 5 6
1 2 10
2 3 10
3 4 10
4 5 2
4 6 3
35
7 7 4 10
5 4 4 7
1 2 100
2 3 100
3 4 10
1 5 80
3 5 30
3 6 10
6 7 5
145
4 5 2 10
2 4
1 2 20
2 4 5
1 3 20
3 4 5
1 4 30
25