Dijkstra算法是一种著名的贪心算法,用于解决单源最短路径问题,即从一个特定源顶点到给定图中的所有其他顶点的最短路径。

这个算法由计算机科学家Edsger W. Dijkstra于1956年构思,三年后发表。

在算法中,我们需要维护一个包含最短路径树中顶点的集合。

在每个步骤中,我们选择一个尚未包含在集合中且与源顶点距离最小的顶点,并将其加入集合。

这样,通过Dijkstra算法,我们逐步生成一个有序的顶点序列,称为Dijkstra序列。

对于给定的图,可能存在多个Dijkstra序列。

例如,{5, 1, 3, 4, 2}和{5, 3, 1, 2, 4}都是给定图的Dijkstra序列。

需要注意的是,序列中的第一个顶点即为指定的特定源顶点。

任务是检查给定的序列是否是Dijkstra序列。

输入格式:

  • 第一行包含两个整数N和M,表示图中的点和边的数量,点的编号为1到N。
  • 接下来M行,每行包含三个整数a, b, c,表示点a和点b之间存在一条无向边,长度为c。
  • 再一行包含整数K,表示需要判断的序列个数。
  • 接下来K行,每行包含一个1到N的排列,表示一个给定序列。

输出格式:

  • 共K行,每行输出第K个序列的判断,如果序列是Dijkstra序列则输出Yes,否则输出No。

数据范围:

  • 1≤N≤1000
  • 1≤M≤105
  • 1≤a, b≤N
  • 1≤c≤100
  • 1≤K≤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

代码实现

#include <iostream>
#include <cstring>
#include <bitset>
using namespace std;
const int N = 1e3 + 10;

int n, m, k, idx, g[N][N], dist[N], st[N], tar[N];
bool isDijkstra() {
    idx = 1;
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[tar[idx]] = 0;
    for (int i = 1; i <= n; ++i) {
        int t = -1;
        for (int j = 1; j <= n; ++j) {
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j; 
        }
        if (!st[tar[idx]] && dist[tar[idx]] == dist[t]) t = tar[idx];
        if (t != tar[idx++]) return 0;
        st[t] = 1;
        for (int j = 1; j <= n; ++j) {
            if (!st[j]) dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
    return 1;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(g, 0x3f, sizeof g);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) g[i][i] = 0;
    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(min(g[a][b], g[b][a]), c);
    }
    cin >> k;
    while(k--) {
        for (int i = 1; i <= n; ++i) cin >> tar[i];
        cout << (isDijkstra() ? "Yes\n" : "No\n");
    }
    return 0;
}
分类: Dijkstra

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status