The government of Spoj_land has
selected number of locations in the city for road construction and numbered
those locations as 0,1,2,3,.......500.
Now, they want to construct roads
between various pairs of location(say a
and b) and have fixed the cost for
travelling between those pair of locations from either end as w
unit.
Now, Rohit being a curious boy wants
to find the minimum cost for travelling from location u (source) to q number of
other locations (destination).
Input. First
line contains n (1 ≤ n ≤ 500), the number of roads that
government constructed.
Next n lines contains three integers a, b
and w (0 ≤ a, b ≤ 500, 1
≤ w ≤ 100).
a and b
represent the locations between which the road was constructed and w is the fixed cost for travelling from a to b
or from b to a.
Next line
contains an integer u from where
Rohit wants to travel to other locations.
Next line
contain q (1 ≤ q ≤ 500), the number of queries
(finding cost) that he wants to perform.
Next q lines contain an integer v (destination) for which minimum cost
is to be found from u (0 ≤ u, v
≤ 500).
Output. Print the
required answer in each line.
If he
can't travel from location u to v by any means then, print 'NO PATH'
without quotes.
|
Sample input |
Sample output |
|
7 0 1 4 0 3 8 1 4 1 1 2 2 4 2 3 2 5 3 3 4 2 0 4 1 4 5 7 |
4 5 9 NO PATH |
алгоритм Дейкстры
Имеется
неориентированный граф из 501 вершины (пронумерованы от 0 до 500). Граф
содержит мультиребра, поэтому среди всех ребер (from, to) в матрицу
смежности следует занести ребро с наименьшим весом.
Далее
следует найти q кратчайших путей из
вершины u. Для этого реализуем
алгоритм Дейкстры.
Реализация алгоритма
#include <stdio.h>
#include <string.h>
#define MAX 510
#define INF 0x3F3F3F3F
int i, j, n, m, u, v, q;
int from, to, len, min, w;
int mas[MAX][MAX], used[MAX],
dist[MAX];
void Relax(int
w, int j)
{
if (dist[w] + mas[w][j] < dist[j])
dist[j] = dist[w] +
mas[w][j];
}
int main(void)
{
n = 501;
scanf("%d",&m);
memset(mas,0x3F,sizeof(mas));
memset(used,0,sizeof(used));
for(i = 1; i <= m; i++)
{
scanf("%d %d %d",&from,&to,&len);
if (len < mas[from][to])
mas[from][to] =
mas[to][from] = len;
}
scanf("%d",&u);
memset(dist,0x3F,sizeof(dist));
dist[u] = 0;
for(i = 1; i < n; i++)
{
min = INF;
for(j = 0; j <= n; j++)
if (!used[j] && dist[j] < min) {min =
dist[j]; w = j;}
for(j = 0; j <= n; j++)
if (!used[j]) Relax(w,j);
used[w] = 1;
}
scanf("%d",&q);
for(i = 0; i < q; i++)
{
scanf("%d",&v);
if (dist[v] == INF) printf("NO
PATH\n");
else printf("%d\n",dist[v]);
}
return 0;
}