超车这个东西这么恶心肯定是要暴力求的(自圆其说)
那么分成一个个时间段来搞，然后DP一下
化一下那个速度，耗费时间是在300s~600s之间的
那我们就可以设f[i][j]为走到第i个位置用了j的时间相遇的最小值
这里有个坑点，就是出发时间和到达时间均相等的两辆车也算相遇。。。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<vector> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int readtime() { int ret=0; for(int i=1,b=3600;i<=3;i++,b/=60) { int k=0;char ch;ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); k=ch-'0';ch=getchar();k=k*10+ch-'0'; ret+=k*b; } return ret; } void writetime(int T) { int k=T/3600;T-=k*3600; if(k<10)printf("0"); printf("%d",k); k=T/60;T-=k*60; if(k<10)printf("0"); printf("%d",k); if(T<10)printf("0"); printf("%d ",T); } //----------------------------------------------------------------------------------------------------- struct car { int st,t; car(){} car(int ST,int T){st=ST,t=T;} }c[310];int L[60],R[60]; int f[60][110000]; int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); int n,m,x,st,t; n=read(),m=read(); for(int i=1;i<=n;i++)L[i]=m+1; for(int i=1;i<=m;i++) { x=read(),c[i].st=readtime(),c[i].t=read(); if(L[x]==m+1)L[x]=i; R[x]=i; } memset(f,63,sizeof(f));f[1][21600]=0; for(int i=1;i<n;i++) for(int j=21600;j<86400;j++) if(f[i][j]!=f[0][0]) { for(int k=300;k<=600;k++) { if(j+k>=86400)break; int sum=0; for(int l=L[i];l<=R[i];l++) if((j+k==c[l].st+c[l].t)||(j<c[l].st&&j+k>=c[l].st+c[l].t)||(j>c[l].st&&j+k<=c[l].st+c[l].t))sum++; f[i+1][j+k]=min(f[i+1][j+k],f[i][j]+sum); } } int mmin=(1<<30),T; for(int j=21600;j<86400;j++) if(f[n][j]<mmin)mmin=f[n][j],T=j; printf("%d ",mmin); writetime(T); return 0; }