Dijkstra 序列
题目描述
Dijkstra
算法是非常著名的贪心算法之一。
它用于解决单源最短路径问题,即指定一个特定源顶点,求该顶点到给定图的所有其他顶点的最短路径。
它由计算机科学家 Edsger W. Dijkstra
于 $1956$ 年构思并在三年后出版。
在该算法中,我们需要不断维护一个包含最短路径树中顶点的集合。
在每一步中,我们找到一个尚未在集合内且与源顶点距离最小的顶点,并将其收于集合中。
因此,通过 Dijkstra
算法,我们可以逐步生成一个有序的顶点序列,我们称之为 Dijkstra 序列
。
对于一个给定的图,可能有多个 Dijkstra 序列
。
例如,$\{ 5, 1, 3, 4, 2 \}$ 和 $\{ 5, 3, 1, 2, 4 \}$ 都是给定图的 Dijkstra 序列
。
注意,序列中的第一个顶点即为指定的特定源顶点。
你的任务是检查给定的序列是否是 Dijkstra 序列
。
输入格式
第一行包含两个整数 $N$ 和 $M$,表示图中点和边的数量。
点的编号 $1 \sim N$。
接下来 $M$ 行,每行包含三个整数 $a, b, c$,表示点 $a$ 和点 $b$ 之间存在一条无向边,长度为 $c$。
再一行包含整数 $K$,表示需要判断的序列个数。
接下来 $K$ 行,每行包含一个 $1 \sim N$ 的排列,表示一个给定序列。
输出格式
共 $K$ 行,第 $i$ 行输出第 $K$ 个序列的判断,如果序列是 Dijkstra 序列
则输出 Yes
,否则输出 No
。
数据范围
$1 \le N \le 1000,$
$1 \le M \le 10 ^ 5,$
$1 \le a, b \le N,$
$1 \le c \le 100,$
$1 \le K \le 100,$
保证给定无向图是连通图,
保证无重边和自环(官网没提,但是经实测,官网数据符合此条件)。
输入样例:
5 7
1 2 2
1 5 1
2 3 1
2 4 1
2 5 2
3 5 1
3 4 1
4
5 1 3 4 2
5 3 1 2 4
2 3 4 5 1
3 2 1 5 4
输出样例:
Yes
Yes
Yes
No
正解:dijkstra
思路
这题思路非常简单,就是对给定的序列分别跑一遍 dijkstra
就好了。
具体实现
构建邻接表。
以给定序列(记为 $a$)的第一项为源点,跑一遍 dijkstra
,在第 $i$ 次取最小值时,如果有多个最小值,应优先取下标为 $a_i$ 的那一项(如果最小值的下标中有 $a_i$ 的话)。取完最小值后,看一看最小值的下标是否为 $a_i$,如果不为 $a_i$,就说明给定序列不是 dijkstra
序列。如果 dijkstra
完没有问题的话,则说明给定序列是 dijkstra
序列。
AC Code
#include <cstdio>
#include <cstring>
#define inf 0x3f
#define N 1005
#define M 100005
using namespace std;
int n, m, k, x, y, z, t, mn, a[N], head[N], nxt[M << 1], ver[M << 1], e[M << 1], d[N], v[N];
void add (int x, int y, int z)
{
ver[++ t] = y, e[t] = z, nxt[t] = head[x], head[x] = t;
return ;
}
void reset ()
{
memset (d, inf, sizeof (d)), memset (v, 0, sizeof (v)), d[a[1]] = 0;
return ;
}
bool dijkstra ()
{
reset ();
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= n; j ++)
{
if (!v[j] && (d[j] < d[x] || j == a[i] && d[j] <= d[x] || v[x]))
{
x = j;
}
}
if (x != a[i])
{
return 0;
}
v[x] = 1;
for (int i = head[x]; i; i = nxt[i])
{
y = ver[i], z = e[i];
if (d[x] + z < d[y])
{
d[y] = d[x] + z;
}
}
}
return 1;
}
int main ()
{
scanf ("%d%d", &n, &m);
while (m --)
{
scanf ("%d%d%d", &x, &y, &z), add (x, y, z), add (y, x, z);
}
scanf ("%d", &k);
while (k --)
{
for (int i = 1; i <= n; i ++)
{
scanf ("%d", &a[i]);
}
puts (dijkstra () ? "Yes" : "No");
}
return 0;
}