10456. Server
Amin and Murad decided to create a “Minecraft”
game server. They invited k guests to their grand opening ceremony. The
invited guests live in different cities and will have a certain ping delay when
connecting to the server (depending on the location). Amin and Murad, realizing
the potential problem, decided to choose the most optimal location for the
server.
There are n cities numbered from 1 to
n and m two-way transmission channels between these cities. You
can connect to the server only through these channels. Through these channels,
you can create a connection between any two cities. However, no two cities can
have more than one canal directly connecting them, and no city has canals
connecting a city to itself. A delay time of wi is also given for each channel. And so, the
delay time for a connection from a city to a server is equal to the smallest
sum of channel delays on the way from this city to a server among all possible
paths.
Amin and Murad want to choose a city for
the server so that the total connection delay of all guests is minimal during
the connection. If the server is located in the city
where some of the guests live, then the connection delay for this guest will be
equal to 0.
If it is possible to select several cities
with a minimum total delay, then Amin and Murad will choose the city with the
lowest number. You need to find the city that Amin and Murad will choose and
the total delay in connecting all guests to the server.
Input. The first line contains three integers n (1 ≤ n ≤ 104), m (1 ≤ m ≤ 4 * 104), k (1 ≤ k ≤ 100) – the number of cities, transmission channels and
guests, respectively. The second line contains k different numbers ci (1 ≤ ci ≤ n) – the numbers of the cities where the guests live. Each of the
following m lines contains three integers ui, vi, wi (1 ≤ ui, vi ≤ n). These numbers indicate a two-way link
between the cities ui and vi with a delayed connection wi (1 ≤ wi ≤ 104).
Output. Print two integers – the number of the city where the
server will be located and the total delay in connecting all guests to this
server.
|
Sample
input |
Sample
output |
|
5 6 3 1 2 5 1 2 10 1 4 3 2 4 2 2 5 8 3 4 5 3 5 3 |
2 13 |
SOLUTION
graphs - Dijkstra
Algorithm analysis
Since n ≤ 104, use an adjacency list to represent the graph.
Start Dijkstra’s algorithm from
the cities in which the guests live. Find the sum of the distances from each vertex to all guests.
The vertex with the smallest sum will be the one we are looking for. If there
are several such vertices, then choose the one with the lowest number.
Note that the
server will not necessarily be located in the city where one of the guests
lives.
Example
The graph given
in the example has a form:
Run Dijkstra’s algorithm from
the vertices where guests live: 1, 2 and 5. Write down the shortest distance from
each guest to all vertices.
Let’s find the sum
of the distances from each vertex to all guests. The smallest sum of distances
is 13. The smallest vertex number for which this sum is achieved is 2.
Thus, the server
should be located in city 2, the distance from it to the guests is 5 + 0 + 8 =
13.
Algorithm realization
Declare an infinity.
#define INF 0x3F3F3F3F
The structure edge stores information about the
edge: which vertex the node goes to and the weight dist of the edge.
struct edge
{
int node, dist;
edge(int node, int dist) : node(node), dist(dist) {}
};
Comparator for sorting pairs (node, dist) in descending
order of dist.
bool operator< (edge a, edge b)
{
return a.dist > b.dist;
}
Declare the adjacency list of the graph.
vector<vector<edge> > g;
The function Dijkstra implements Dijkstra’s algorithm. The input is the graph g and the initial vertex start.
The return value is an array d, where d[i] contains the shortest
distance from start to i.
void Dijkstra(vector<vector<edge> >& g, vector<int>& d, int start)
{
priority_queue<edge> pq;
pq.push(edge(start, 0));
d = vector<int>(n + 1, INF);
d[start] = 0;
while (!pq.empty())
{
edge e = pq.top();
pq.pop();
int v = e.node;
if (e.dist > d[v]) continue;
for (int j = 0; j < g[v].size(); j++)
{
int to = g[v][j].node;
int cost = g[v][j].dist;
if (d[v] + cost < d[to])
{
d[to] = d[v] + cost;
pq.push(edge(to, d[to]));
}
}
}
}
The main part of the program. Read the input data.
scanf("%d %d %d", &n, &m,
&k);
c.resize(k);
for (i = 0; i < k; i++)
scanf("%d", &c[i]);
Read the input weighted graph.
g.resize(n + 1);
for (i = 0; i < m; i++)
{
scanf("%d %d %d", &a, &b, &w);
g[a].push_back(edge(b, w));
g[b].push_back(edge(a, w));
}
Run Dijkstra’s algorithm from the cities where the guests live.
dp.resize(n + 1);
for (i = 0; i < k; i++)
{
Dijkstra(g, dist, c[i]);
for (j = 1; j <= n;
j++)
dp[j] += dist[j];
}
At the moment, dp[i] stores the sum of the shortest
distances from vertex i to cities with guests. It remains to find the
minimum value among dp[i] and print the required answer. The ptr
variable stores the smallest vertex number where the server should be located.
res = INF;
for (i = 1; i <= n; i++)
{
if (dp[i] < res)
{
res = dp[i];
ptr = i;
}
}
Print the answer.
printf("%d %d\n", ptr, dp[ptr]);