Dijkstra序列问题判段

堆优化版dijkstra

满分

/**
题意:判断是否是dijkstra序列

难点:怎么来判断呢?(自己模拟一下即可)
3 2 1 5 4 因为2到1不是最短路径,所以错误

方案1: 每个初始点,模拟一把dijkstra, 看每一步是否是最短路径

用一次领接表实现吧
*/
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int N = 1010, M = 2 * 100010;
int e[M], w[M], ne[M], h[N], cnt;
int dist[N];
bool st[N];
void add(int a, int b, int c)
{
    e[cnt] = b, w[cnt] = c, ne[cnt] = h[a], h[a] = cnt++;
}
typedef pair<int, int> PII;
void dijkstra(int s)
{
    memset(st, false, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PII, vector<PII>, greater<>> heap;
    dist[s] = 0;
    heap.push({0, s});
    while (!heap.empty())
    {
        auto t = heap.top();
        heap.pop();
        int u = t.second;
        if (st[u]) continue;
        st[u] = true;

        for(int i = h[u]; ~i; i = ne[i])
        {
            int v = e[i];
            if (dist[v] > dist[u] + w[i])
            {
                dist[v] = dist[u] + w[i];
                heap.push({dist[v], v});
            }
        }
    }
}
int main()
{
    int m, n, q;
    cin >> m >> n;
    memset(h, -1, sizeof h);
    while (n --)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    cin >> q;
    while (q--)
    {
        vector<int> vc(m + 1);
        for(int i = 0; i < m; i++) cin >> vc[i];
        dijkstra(vc[0]);
        int front = dist[vc[0]];
        bool flag = true;
        for(int i = 1; i < m; i++)
        {
            if (dist[vc[i]] < front)
            {
                flag = false;
                break;
            }
            front = dist[vc[i]];
        }
        if (flag) printf("Yes\n");
        else printf("No\n");
    }
}

方法二 25分, 一个点超时

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int M = 1010, N = 200010;
int h[M], e[N], ne[N], w[N], cnt;
int d[M];
bool visit[M];
int m, n, q;
void add(int a, int b, int c)
{
    w[cnt] = c, e[cnt] = b, ne[cnt] = h[a], h[a] = cnt++;
}

void dijkstra(int start)
{
    memset(d, 0x3f, sizeof d);
    memset(visit, false, sizeof visit);
    priority_queue<int, vector<int>, greater<int>> heap;
    heap.push(start);
    d[start] = 0;
    while (heap.size())
    {
        auto it = heap.top();
        heap.pop();
        int ver = it;
        for(int i = h[ver]; ~i; i = ne[i])
        {
            int next = e[i];
            if (d[next] > d[ver] + w[i])
            {
                d[next] = d[ver] + w[i];
                heap.push(next);
            }
        }
    }
}
int main()
{
    memset(h, - 1, sizeof h);
    cin >> m >> n;
    for(int i = 0; i < n; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    cin >> q;
    while (q --)
    {
        vector<int> res(m);
        bool flag = true;
        for(int i = 0; i < m; i++) cin >> res[i];
        dijkstra(res[0]);
        int min_n = -1;
        for(int i = 0; i < m; i++)
        {
            if (d[res[i]] >= min_n) min_n = d[res[i]];
            else flag = false;
        }
        if (flag) puts("Yes");
        else puts("No");
    }
}

方法一 , 满分

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int,int> PII;
const int N = 1010;
int g[N][N], dist[N];
bool visit[N];
int m, n, k;

void dijkstra(int s)
{
    memset(dist, 0x3f, sizeof dist);
    memset(visit, false, sizeof visit);
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, s});
    dist[s] = 0;
    while (heap.size())
    {
        auto it = heap.top();

        int ver = it.second;
        visit[ver] = true;
        heap.pop();
        for(int i = 1; i <= m; i++)
        {
            if (visit[i] == false && dist[i] > dist[ver] + g[ver][i])
            {
                dist[i] = dist[ver] + g[ver][i];
                heap.push({dist[i], i});
            }
        }
    }
}
void check(vector<int> &res)
{
    int min_num = -1;
    for(int i = 0; i < res.size(); i++)
    {
        if (dist[res[i]] > min_num)
        {
            min_num = dist[res[i]];
        }else if (dist[res[i]] < min_num){
            printf("No\n");
            return;
        }
    }
    printf("Yes\n");
}

int main()
{
    memset(g, 0x3f, sizeof g);
    cin >> m >> n;
    for(int i = 0; i < n; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = c;

    }
    cin >> k;
    while (k --)
    {
        vector<int> res(m);
        for(int i = 0; i < m; i++) cin >> res[i];
        dijkstra(res[0]);

        // 判断是否最短路
        check(res);
    }

}