摘要
Title: 4275. Dijkstra序列
Tag: dijkstra
Memory Limit: 64 MB
Time Limit: 1000 ms

4275. Dijkstra序列

题意

Dijkstra 算法是非常著名的贪心算法之一。
它用于解决单源最短路径问题，即指定一个特定源顶点，求该顶点到给定图的所有其他顶点的最短路径。
它由计算机科学家 Edsger W. Dijkstra 于 1956 年构思并在三年后出版。
在该算法中，我们需要不断维护一个包含最短路径树中顶点的集合。
在每一步中，我们找到一个尚未在集合内且与源顶点距离最小的顶点，并将其收于集合中。
因此，通过 Dijkstra 算法，我们可以逐步生成一个有序的顶点序列，我们称之为 Dijkstra 序列。
对于一个给定的图，可能有多个 Dijkstra 序列。
例如，{5,1,3,4,2} 和 {5,3,1,2,4} 都是给定图的 Dijkstra 序列。
注意，序列中的第一个顶点即为指定的特定源顶点。
你的任务是检查给定的序列是否是 Dijkstra 序列。
思路

结论：合法的dijkstra序列等价于 dist[]单调递增的序列

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-06-20 23:39:01
* @FilePath: \ACM\Acwing\4275\4275.cpp
* @LastEditTime: 2022-06-21 09:41:00
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<int, int> PII;

const int INF = INT_MAX;
const int N = 1e6 + 10;

signed main()
{
    IOS;
    int n, m;
    cin >> n >> m;

    vector<PII> g[n + 1];

    for (int i = 1; i <= m; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    auto dij = [&](vector<int> qq) {
        int s = qq[0];

        vector<int> st(n + 1);
        vector<int> dist(n + 1, INF);
        priority_queue<PII, vector<PII>, greater<PII>> q;
        q.push({0, s});
        dist[s] = 0;

        while (SZ(q))
        {
            auto [dis, u] = q.top();
            q.pop();

            if (st[u])
                continue;
            st[u] = 1;
            for (auto [v, w] : g[u])
            {
                if (dist[v] > dist[u] + w)
                {
                    dist[v] = dist[u] + w;
                    q.push({dist[v], v});
                }
            }
        }

        for (int i = 0; i < n - 1; ++i)
        {
            if (dist[qq[i]] > dist[qq[i + 1]])
                return 0;
        }
        return 1;
    };

    int k;
    vector<int> q(n);
    cin >> k;
    while (k--)
    {
        for (int i = 0; i < n; ++i)
        {
            cin >> q[i];
        }
        if (dij(q))
            cout << "Yes\n";
        else
            cout << "No\n";
    }

    return 0;
}

4275. Dijkstra序列

题意

思路

代码