核心:拓扑排序判定是否有环

dijkstra来判断最短路, 分数最小, 优惠券最多

复制方法, vector<-int> vc(ind, ind + N);

满分 用虚拟原点实现

易错的习惯, 首先就是将所有的测试数据放入了vector数组中,但是调用的时候,没有用vector数组中的值

而是用了for循环中的索引i, 及其难找的错误

/**

拓扑排序是用来干嘛的?

难点:拓扑排序时间复杂度是多少?
最多有1000个query
需要入度和出度,判断是否有前置test

还要用dijkstra判定是否最小的分数, 最大的优惠

步骤1 :拓扑排序判断是否有环?
*/
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int N = 1010, M = 1000010;
int e[M], w[M], vc[M], ne[M], h[N], cnt;
int ind[N], copyd[N]; // 入度和备份
int dist[N], voucher[N], p[N];
bool st[N];
void add(int a, int b, int c, int d)
{
    e[cnt] = b, w[cnt] = c, vc[cnt] = d, ne[cnt] = h[a], h[a] = cnt++;
}
typedef pair<int, int> PII;

int m, n;
void dijkstra(int s)
{
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0, voucher[s] = 0;
    priority_queue<PII, vector<PII>, greater<>> heap;
    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];
                voucher[v] = voucher[u] + vc[i];
                p[v] = u;
                heap.push({dist[v], v});
            }else if (dist[v] == dist[u] + w[i] && voucher[v] < voucher[u] + vc[i])
            {
                voucher[v] = voucher[u] + vc[i];
                p[v] = u;
            }
        }
    }
}
bool ff = true;
void dfs(int u)
{
    if (p[u] != u) dfs(p[u]);

    if (u != m)
    {
        if (ff) ff = false;
        else printf("->");
        printf("%d", u);
    }

}
bool tropical_order(int u)
{
    // 难点:拓扑排序如何实现
    vector<int> res;
    res.push_back(u);
    for(int i = 0; i < res.size(); i++)
    {
        int v = res[i];
        for(int j = h[v]; ~j; j = ne[j])
        {
            int x = e[j];
            copyd[x]--;
            if (copyd[x] == 0) res.push_back(x);
        }

    }
    return res.size() == m + 1;
}
int main()
{

    cin >> m >> n;
    memset(h, -1, sizeof h);
    while (n --)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        add(a, b, c, d);
        ind[b]++;
        copyd[b]++;
    }
    for(int i = 0; i < m; i++)
    {
        if (!ind[i])
        {
            // 建立虚拟原点
            //root = i;
            add(m, i, 0, 0);
            ind[i]++;
            copyd[i]++;
        }
    }
    // 选一个入度为0
    bool flag = tropical_order(m);

    if (!flag) printf("Impossible.\n");
    else printf("Okay.\n");

    int q;
    cin >> q;
    vector<int> res(q + 1);
    for(int i = 0; i < q; i++) cin >> res[i];

    // 建立虚拟原点, 一次dijkstra保存到所有点的最短路径
    for(int i = 0; i <= m; i++) p[i] = i;
    dijkstra(m);
    for(int i = 0; i < q; i++)
    {
        if (ind[res[i]] == 1 && p[res[i]] == m) printf("You may take test %d directly.\n", res[i]);
        else
        {
            if (!flag) printf("Error.\n");
            else{
                // dfs(i);  这一步调试了2h
                dfs(res[i]);
                ff = true;
                printf("\n");
            }

        }
    }


}

满分代码

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

typedef pair<int,int> PII;

const int N = 1010, M = 1000010;

int h[N], e[M], ne[M], s[M], vou[M], cnt;
bool st[N], visit[N];
int path[N], d[N], fee[N]; // 距离和费用
int degree[N]; // 入度
vector<int> vc;
int m, n, k;

void add(int a, int b, int score, int d)
{
    e[cnt] = b, ne[cnt] = h[a], s[cnt] = score, vou[cnt] = d, h[a] = cnt++;
}

void dijkstra()
{
    memset(d, 0x3f, sizeof d);
    memset(fee, 0x3f, sizeof fee);
    memset(path, -1, sizeof path);
    priority_queue<PII, vector<PII>, greater<>> heap;
    for(int i = 0; i < vc.size(); i++)
    {
        d[vc[i]] = 0; // 初始化度为0节点
        fee[vc[i]] = 0;
        heap.push({0, vc[i]});
    }
    while(heap.size())
    {
        auto it = heap.top();
        heap.pop();
        int u = it.second;
        if (visit[u]) continue;
        visit[u] = true;
        for(int i = h[u]; ~i; i = ne[i])
        {
            int y = e[i];
            if (d[y] > d[u] + s[i])
            {
                d[y] = d[u] + s[i];
                fee[y] = fee[u] + vou[i];
                path[y] = u;
                heap.push({d[y], y});
            }else if (d[y] == d[u] + s[i] && fee[y] < fee[u] + vou[i])
            {
                fee[y] = fee[u] + vou[i];
                path[y] = u;
            }
        }
    }

}

bool tropic_sort()
{
    queue<int> q;
    int count = 0;
    for(int i = 0; i < vc.size(); i++)
    {
        q.push(vc[i]);
        count++;
    }


    while (q.size())
    {
        int u = q.front();
        q.pop();
        for(int i = h[u]; ~i; i = ne[i])
        {
            int y = e[i];
            degree[y]--;
            if (degree[y] == 0) {
                q.push(y);
                count++;
            }
        }
    }
    if (count == m) return true;
    else return false;
}
int main()
{

    memset(h, -1, sizeof h);
    cin >> m >> n;
    for(int i = 0; i < n; i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        add(a, b, c, d);
        st[b] = true;
        degree[b]++;
    }
    for(int i = 0; i < m; i++)
    {
        if (!st[i]) vc.push_back(i);
    }
    // 先判断是否有环??拓扑排序呀
    bool result = tropic_sort();
    cin >> k;
    dijkstra();
    if (result) puts("Okay.");
    else puts("Impossible.");
    for(int i = 0; i < k; i++)
    {
        int x;
        cin >> x;
        if (!st[x]) printf("You may take test %d directly.\n", x);
        else{
            if (!result) printf("Error.\n");
            else {
                vector<int> res;
                for(int j = x; j != -1; j = path[j])
                {
                    res.push_back(j);
                }
                for(int j = res.size() - 1; j >= 0; j--)
                {
                    printf("%d", res[j]);
                    if (j != 0) printf("->");
                }
                puts("");
            }

        }
    }
}