PAT 2020年秋季考试最后一题

原题

样例

Sample Input 1:
8 15
0 1 50 50
1 2 20 20
3 4 90 90
3 7 90 80
4 5 20 20
7 5 10 10
5 6 10 10
0 4 80 60
3 1 50 45
1 4 30 20
1 5 50 20
2 4 10 10
7 2 10 30
2 5 30 20
2 6 40 60
8
0 1 2 3 4 5 6 7
Sample Output 1:
Okay.
You may take test 0 directly.
0->1
0->1->2
You may take test 3 directly.
0->1->2->4
0->1->2->4->5
0->1->2->6
3->7

Sample Input 2:
4 5
0 1 1 10
1 2 2 10
3 0 4 10
3 2 5 10
2 0 3 10
2
3 1
Sample Output 2:
Impossible.
You may take test 3 directly.
Error.

解题思路

/*大体思路如下：详细看代码注释吧
1、首先进行拓扑排序，要在输入的时候就每个节点的入度inDegree，为了区分有没有环！然后先完成样例二的输出，但是在输出时发现inDegree被修改，所以在输入的时候要在保存一个入度数组indeg，从而当入度为零的时候直接输出You may take test 3 directly.
2、经过第一步程序分为两个分支，如果有环，且入度为0，就输出You may take test 3 directly.，不为零就输出Error
3、然后再处理没有环的部分，同样在入度为0时打印You may take test 3 directly.，入度不为0需要计算到这个需要查询的点的最短距离。
4、已知图的终点求最短路径，用《算法笔记》上的Dijkstra不合适，然后考虑到后面动态规划有一个求DAG求最长路的解法，可以实现已知起点，未知终点求最长路径，这里将其修改。
5、在修改的时候要注意初始化边界问题，也就是dp数组，因为是求最小值，所以将dp数组全部初始化为INF，但是在递归到边界时，返回的也是INF，这明显不合理，所以在递归到边界的时候，如果dp[i]==INF,需要返回0，这样在递归完一层返回的时候，int temp=DP(j)+G[j][i];才是从初始化位置开始的最小值！这里还需要注意，每一层当前的节点为i，然后要遍历能够到达该点的前驱节点，所以使用G[j][i]!!!
6、以上就是大致思路，测试点全部ac，但应该还可以更加优化！
*/

代码

#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;
typedef long long ll;
const int maxn = 1010, INF = 1e9;
int n, m, G[maxn][maxn], d[maxn], S[maxn], D[maxn][maxn], dd[maxn];
int inDegree[maxn], query[maxn], indeg[maxn], dp[maxn];
bool vis[maxn] = {false};
int pre[maxn];

//拓扑排序判断是否有环
bool topoSort() {
    int num = 0;
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int i = q.front();
        q.pop();
        for (int j = 0; j < n; j++) {
            if (G[i][j] != INF) {
                inDegree[j]--;
                if (inDegree[j] == 0) {
                    q.push(j);
                }
            }
        }
        num++;
    }
    if (num == n) return true;
    else return false;
}
//动态规划求解已知终点，未知起点最短路径，当路径长度相同时，根据voucher的边权和判断，选择大的一条
int DP(int i) {
    if (vis[i]) {
        if (dp[i] == INF) return 0;//递归到边界，返回0
        else return dp[i];
    }
    vis[i] = true;
    for (int j = 0; j < n; j++) {
        if (G[j][i] != INF) {//这里使用G[j][i],i是当前节点，j是每一个前驱节点
            int temp = DP(j) + G[j][i];//开始递归前驱节点，直到边界，也就是最开始的节点
            if (temp < dp[i]) {
                dp[i] = temp;//保存最短路径
                pre[i] = j;//保存前驱节点
                dd[i] = dd[j] + D[j][i];//保存当前路径的voucher和
            } else if (temp == dp[i]) {
                if (dd[j] + D[j][i] > dd[i]) {//如果路径长度相等，继续判断voucher大的为前驱即可
                    dd[i] = dd[j] + D[j][i];
                    pre[i] = j;
                }
            }
        }
    }
    if (dp[i] == INF) return 0;//这里返回的时候要注意，如果没有前驱，也就是到了边界，要返回0
    else return dp[i];
}
//递归打印路径
void printPath(int v) {
    if (pre[v] == -1) {//先递归到第一个节点
        printf("%d", v);
        return;
    }
    printPath(pre[v]);
    printf("->%d", v);//依次打印
}

int main() {
    fill(G[0], G[0] + maxn * maxn, INF);
    fill(inDegree, inDegree + maxn, 0);
    fill(indeg, indeg + maxn, 0);
    fill(dp, dp + maxn, 0);
    fill(pre, pre + maxn, -1);
    scanf("%d%d", &n, &m);
    int t1, t2, s1, d1;
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d%d", &t1, &t2, &s1, &d1);
        G[t1][t2] = s1;
        D[t1][t2] = d1;
        inDegree[t2]++;//入度
        indeg[t2]++;
    }
    int k;
    scanf("%d", &k);
    for (int i = 0; i < k; i++) scanf("%d", &query[i]);
    //先通过拓扑排序判断其是否有环
    bool isNoHuan = topoSort();
    if (!isNoHuan) {
        printf("Impossible.\n");
        for (int i = 0; i < k; i++) {
            if (indeg[query[i]] == 0) {
                printf("You may take test %d directly.\n", query[i]);
            } else {
                printf("Error.\n");
            }
        }
    } else {
        printf("Okay.\n");
        for (int i = 0; i < k; i++) {
            if (indeg[query[i]] == 0) {
                printf("You may take test %d directly.\n", query[i]);
            } else {
                //因为每次都是从一个新的终点求一条新的最短路径，所以这些数组必须重新初始化！
                fill(dp, dp + maxn, INF);
                fill(vis, vis + maxn, false);
                fill(dd, dd + maxn, 0);
                fill(pre, pre + maxn, -1);//前驱节点初始化
                DP(query[i]);
                printPath(query[i]);
                printf("\n");
            }
        }
    }
    return 0;
}