34. The word of sponsor
At the end of the tournament
The
New-Year Night, the sponsor decided to send the presents to m prize-winners by
post. You know the number of competitors n and the delivering time for
post between some departments of Ukrpost. Find the time when
the last prize-winner will receive his prize.
Input. In the first line we have 3 integers:
the number of tournament competitors n, the
number of prizes from sponsor m and
the number of known delivering time k for post
between some departments. In next line we have the number of competitors, who
became prize-winners. These numbers are separated with a space.
Each of the next k lines
contains 3 numbers and describe the information about known
delivering time for post between some departments in format: a b t where a and b are numbers of
departments, t
(0 ≤ t ≤ 365) is time of
delivering for post between some departments.
The last line gives the post
department number, where from the sponsor will send his presents. It is known
that 1 ≤ n, m, a, b
≤ 365.
Output. If all presents will be
deliver to competitors than make clear in first line The good sponsor!, and in next line
male clear through what time the least of prize-winners will receive his prize.
If one of competitors cant receive his prize than you must make clear in one
line It
is not fault of sponsor.... The phrases make clear without quotation marks.
|
Samle input |
Sample output |
|
3 2 2 2 3 1 2 3 2 3 4 1 |
The good sponsor! 7 |
SOLUTION
graphs Dijkstra
Algorithm analysis
Consider
a graph which vertices
are post offices, and the weights of the edges are the delivery time between
them. In this problem
you must find the lengths of the shortest
paths from the post office, from which the sponsor sends the prizes, to the
winners. This can be done using Dijkstras
algorithm. The time after which the last of the winners will receive his prize
equals to the maximum among the found
lengths of the shortest paths.
Examples
Consider
the graph given in the sample. The
sponsor sends prizes from vertex 1. The winners are located at vertices 2 and
3.
Algorithm realization
Declare constants and arrays to implement Dijkstras algorithm. The numbers of the participants who have
become prize winners
will be stored in array priz.
#define MAX 400
#define INF
0x3F3F3F3F
int
mas[MAX][MAX], used[MAX], d[MAX];
int priz[MAX];
Read the input data.
scanf("%d %d
%d",&n,&m,&k);
for(i = 1; i
<= m; i++) scanf("%d",&priz[i]);
Build the input graph. Initialize
the variables.
memset(mas,63,sizeof(mas));
memset(used,0,sizeof(used));
for(i = 1; i
<= k; i++)
{
scanf("%d %d %d",&b,&e,&dist);
mas[b][e] = mas[e][b] = dist;
}
memset(d,0x3F,sizeof(d));
scanf("%d",&source);
d[source] = 0;
Start the Dijkstras
algorithm.
for(i = 1; i
< n; i++)
{
min =
INF;
for(j = 1; j <= n; j++)
if (!used[j] && d[j] < min) {min = d[j]; w
= j;}
for(j = 1; j <= n; j++)
if (!used[j]) d[j] = minimum(d[j],d[w] + mas[w][j]);
used[w]
= 1;
}
Find the
longest time after which all winners will receive their prizes.
mx = 0;
for(i = 1; i
<= m; i++)
if (d[priz[i]] > mx) mx = d[priz[i]];
If this time equals
to infinity, then some of the participants will not receive a prize.
if (mx ==
INF) printf("It is not fault of
sponsor...\n");
else printf("The good
sponsor!\n%d\n",mx);
Java realization
import java.util.*;
public class Main
{
static final int INFINITY = 2000000000;
static int g[][], used[], dist[], priz[];
static void Relax(int i, int j)
{
if (dist[i] + g[i][j] < dist[j])
dist[j] = dist[i] + g[i][j];
}
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt();
int m = con.nextInt();
int k = con.nextInt();
g = new int[n+1][n+1];
for (int[] row: g) Arrays.fill(row, INFINITY);
priz = new int[n+1];
for(int i = 1; i <= m; i++)
priz[i] = con.nextInt();
for (int i = 1; i <= k; i++)
{
int b = con.nextInt();
int e = con.nextInt();
int dist = con.nextInt();
g[b][e] = g[e][b] = dist;
}
used = new int[n+1];
dist = new int[n+1]; Arrays.fill(dist, INFINITY);
int source = con.nextInt();
dist[source] = 0;
for (int i = 1; i < n; i++)
{
// find vertex w with minimum d[w] among not used vertices
int min = INFINITY, v = -1;
for (int j = 1; j <= n; j++)
if (used[j] == 0 && dist[j] < min) { min = dist[j]; v = j; }
// no more vertices to add
if (v < 0) break;
// relax all edges outgoing from v
// process edge v -> j
for (int j = 1; j <= n; j++)
if (used[j] == 0) Relax(v, j);
// shortest distance to v is found
used[v] = 1;
}
int max = 0;
for(int i = 1; i <= m; i++)
if (dist[priz[i]] > max) max = dist[priz[i]];
if (max == INFINITY) System.out.println("It is
not fault of sponsor...");
else System.out.println("The good sponsor!\n" + max);
con.close();
}
}