看着楼上 dalao 的最短路，本蒟蒻直接不会了，本蒟蒻只会爆搜。
题目简述
给定一个有向图，它的边有二特殊性质，及可在奇数天通过或在偶数天通过，以及一边只得在同一天通过。要求给出一条一天之中边权和不超过 $ 12 $ 且最短的路径。
分析
观察数据范围，我们发现 $ n \le 100 $，直接暴力搜索。
具体做法
对于每一条路径，记 $ tot $ 为总小时数 $ day $ 为总天数，$ time $ 为当天小时数。
那么，简单分析可得，对于一条路径上的一个点，只有两种选择：
枚举与他相邻的每一条边，当 $ time + \text{边权} \le 12 $ 且当天可过，则直接继续 dfs。
等待一天，继续 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++！！！
