我的程序在样例上运行的时候结果是

1 6 1 2
6 4 2 2
4 3 3 4

这种解应该是可行的，而且比样例走的路径更短，是更优的解，我认为应当开 $Special Judge$。

我的算法提交后只过了一个点

代码:

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

using namespace std;

int day = 0, lt = 0;
const int N = 150;
int g[N][N], t[N], pre[N], ans[N][10]; //起， 终， 第几天， 当天时间 
queue<int> q1, q2; //正，反
int n, k;

inline void print_dfs(int dep) {
    if(pre[dep] != 0) {
        print_dfs(pre[dep]);
        printf("%d %d %d %d\n", ans[dep][0], ans[dep][1], ans[dep][2], g[pre[dep]][dep] ? g[pre[dep]][dep] : g[dep][pre[dep]]);
    }
}

inline void dfs(int x, int t, bool fl) {
    if(fl) {
        for(int i = 1; i <= n; i++) {
            if(i != x) {
                if(g[x][i] != 0 && lt - t >= g[x][i]) {
                    if(ans[i][3] > ans[x][3] + g[x][i]) {
                        ans[i][3] = ans[x][3] + g[x][i];
                        q1.push(i);
                        q2.push(i);
                        pre[i] = x;
                        ans[i][2] = day;
                        ans[i][0] = x;
                        ans[i][1] = i;
                        dfs(i, ans[i][3], fl);
                    }
                }
            }
        }
    } else {
        for(int i = 1; i <= n; i++) {
            if(i != x) {
                if(g[i][x] != 0 && lt - t >= g[i][x]) {
                    if(ans[i][3] > ans[x][3] + g[i][x]) {
                        ans[i][3] = ans[x][3] + g[i][x];
                        q1.push(i);
                        q2.push(i);
                        pre[i] = x;
                        ans[i][2] = day;
                        ans[i][0] = x;
                        ans[i][1] = i;
                        dfs(i, ans[i][3], fl);
                    }
                }
            }
        }
    }
}

int main() {
    int city_a, city_b;
    scanf("%d%d%d%d", &city_a, &city_b, &n, &k);

    //初始化
    for(register int i = 1; i <= n; i++) {
        for(register int j = 1; j <= n; j++) {
            g[i][j] = 0;
        }
        ans[i][3] = 2147483647;
    }
    lt = 0;

    for(int i = 1; i <= k; i++) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        g[x][y] = c;
    }

    q1.push(city_a);
    q2.push(city_a);
    ans[city_a][3] = 0;

    while(!q1.empty() || !q2.empty()) {
        //正向
        lt += 12;
        day++;
        while(!q1.empty()) {
            int now = q1.front();
            q1.pop();
            for(int i = 1; i <= n; i++) {
                if(i != now) {
                    if(g[now][i] != 0 && lt - ans[now][3] >= g[now][i]) { 
                        if(ans[i][3] > ans[now][3] + g[now][i]) {
                            ans[i][3] = ans[now][3] + g[now][i];
                            q1.push(i);
                            q2.push(i);
                            pre[i] = now;
                            ans[i][2] = day;
                            ans[i][0] = now;
                            ans[i][1] = i;
                            dfs(i, ans[i][3], true);
                        }
                    } 
                }
            }
        }
        //反向
        lt += 12;
        day++;
        while(!q2.empty()) {
            int now = q2.front();
            q2.pop();
            for(int i = 1; i <= n; i++) {
                if(i != now) {
                    if(g[i][now] != 0 && lt - ans[now][3] >= g[i][now]) {
                        if(ans[i][3] > ans[now][3] + g[i][now]) {
                            ans[i][3] = ans[now][3] + g[i][now];
                            q1.push(i);
                            q2.push(i);
                            pre[i] = now;
                            ans[i][2] = day;
                            ans[i][0] = now;
                            ans[i][1] = i;
                            dfs(i, ans[i][3], false);
                        }
                    }
                }
            }
        }
    }
    print_dfs(city_b);
    system("pause");
    return 0;
}