看着楼上 dalao 的最短路，本蒟蒻直接不会了，本蒟蒻只会爆搜。

题目简述

给定一个有向图，它的边有二特殊性质，及可在奇数天通过或在偶数天通过，以及一边只得在同一天通过。要求给出一条一天之中边权和不超过 $ 12 $ 且最短的路径。

分析

观察数据范围，我们发现 $ n \le 100 $，直接暴力搜索。

具体做法

对于每一条路径，记 $ tot $ 为总小时数 $ day $ 为总天数，$ time $ 为当天小时数。

那么，简单分析可得，对于一条路径上的一个点，只有两种选择：

1. 枚举与他相邻的每一条边，当 $ time + \text{边权} \le 12 $ 且当天可过，则直接继续 dfs。

2. 等待一天，继续 dfs。

存图时建议使用链式前向星，在枚举邻边时较快。

特别强调，要建 双向边 。

最后就是无脑 dfs 了。

Code

#include<bits/stdc++.h>
using namespace std;
int max(int a,int b){
    return a>b?a:b;
}
int min(int a,int b){
    return a<b?a:b;
}//自带min,max太慢了，小优化
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-'){
            f=-1;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    return x*f;
}//快读
void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9){
        write(x/10);
    }
    putchar(x%10+'0');
    return;
}//快写
int a,b,n,m,u,v,x,head[101],sum,i,cnt,ans=0x3f3f3f3f,tot,sda;//a为出发点，b为目标点，n为城市数，m为节点数，u为出发城市，v为到达城市，x为走过道路花费的时间，cnt为每一次dfs时经过的城市数，ans为最小花费小时数，tot为每一次dfs时花费的小时数，sda为最小花费时经过的城市数
bool vis[101];//标记城市是否被访问过
struct node{
    int to,nxt,num,flag;//链式前向星结构体，flag为奇偶标志
};
node e[2001];
void add(int a,int b,int c,int d){
    e[++sum].num=c;
    e[sum].to=b;
    e[sum].nxt=head[a];
    e[sum].flag=d;
    head[a]=sum;
}//链式前向星建图
struct dot{
    int fr,to,num,day;
};
dot cit[101],well[101];//按输出要求，fr为出发编号，to为到达编号，num为道路长度，day为日期
void dfs(int x,int day,int t,int skiped){//x为当前到达城市，day为日期，t为时间（当天的第几小时），skiped为停留次数
    int i;
    if(tot>ans){//一个小优化，如果当前花费时间大于当前最优解，直接return
        return ;
    }
    if(x==b){
        if(ans>tot){//更新最优解
            sda=cnt;
            ans=tot;
            for(i=1;i<=cnt;i++){
                well[i].day=cit[i].day,well[i].fr=cit[i].fr,well[i].to=cit[i].to,well[i].num=cit[i].num;
            }
        }
        return;
    }
    //当天不停留继续旅行
    for(i=head[x];i!=0;i=e[i].nxt){//遍历每一条相邻的边
        if(!vis[e[i].to]&&day%2==e[i].flag&&t+e[i].num<=12){//如果边连接的点没访问过&&当天可通行&&加上这条边后当天旅行时间<=12就访问该点
            tot+=e[i].num;//加上花费时间
            vis[e[i].to]=true;//标记访问过
            cit[++cnt].fr=x;//记录答案
            cit[cnt].to=e[i].to,cit[cnt].num=e[i].num,cit[cnt].day=day;
            dfs(e[i].to,day,t+e[i].num,0);//继续dfs
            cnt--;//回溯
            vis[e[i].to]=false;
            tot-=e[i].num;
        }
    }
    //停留一天
    tot+=24-t;//+24-t与当天时间t相加，得24小时，等于第二天0:00出发
    if(skiped<2){//若停留次数大于等于2，就不如不停
        dfs(x,day+1,0,skiped+1);//停留一天继续走
    }
    tot-=24-t;//回溯
    return ;
}
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    a=read();
    b=read();
    n=read();
    m=read();
    for(i=1;i<=m;i++){
        u=read();
        v=read();
        x=read();
        add(u,v,x,1);//正向建一条u到v边权为x，奇数天可以通过的边
        add(v,u,x,0);//反向建一条偶数天可以通过的边
    }
    dfs(a,1,0,0);//无脑dfs
    for(i=1;i<=sda;i++){//输出
        write(well[i].fr);
        putchar(' ');
        write(well[i].to);
        putchar(' ');
        write(well[i].day);
        putchar(' ');
        write(well[i].num);
        putchar('\n');
    }
    return 0;
}

本蒟蒻第一篇题解，管理员大大求过！！！

最后祝大家NOIP2024 rp++！！！