这个OJ比较折腾，中文注释什么的都要注意，本来代码是1Y的，但是因为中文注释的问题CE和TLE了无数次，把中文注释消掉一部分后就AC了，一位同学说是中文注释的换行问题，所以如果这个代码copy过去不能AC而是什么CE,TLE甚至WA的话，那不是代码的问题应该是一些细节问题，可以搞搞中文注释什么的大概就过了
最短路径的变形
给出有向边u->v，后面跟两个数据一个是走这条边要用的时间，之后是到达v点后会有红绿灯，每次红绿灯的时间，，一开始所有红绿灯都是从红灯开始的
用dij算法来时间，具体的做法只是修改了一下dij算法的模板
//判断红绿灯的方法是 当前是时间t和这个点的红绿灯时间w//(t/w)%2==1,为绿灯，即取下整后再模2为奇数
//(t/w)%2==0,为红灯，即取下整后模2为偶数,还需要等待的时间为w-t%(2w)
//所以写一个green_or_red（）函数来判断红绿灯，返回0表示红灯还要等待，返回1表示绿灯可以直接离开
//另外要注意有些点的红绿灯的时间为0，这个点相当于全部是绿灯不用等待，不能用green_or_red()函数来判断因为会除0出错，直接归为绿灯即可
从出发开始计时，到达点v的时间知道，然后看此时是否是红灯，是的话要加上还需等待的时间才是真正到达这个点的时间，然后就没有什么特别了就是dij
#include <stdio.h> #include <string.h> #define N 30 #define INF 0x7fffffff struct graph { int t1,t2; }g[N][N]; int n,m; int V0,V; int D[N],cov[N],path[N]; int find(char node[] , char s[]) { int i=1; if(node[i]=='\0') //第一个顶点 { node[i]=s[0]; node[i+1]='\0'; return i; } for(i=1; node[i]!='\0'; i++) if(node[i]==s[0]) return i; node[i]=s[0]; node[i+1]='\0'; return i; } void input() { char s1[10],s2[10]; char node[N]; int i,j,t1,t2,x1,x2; scanf("%d",&m); for(i=0; i<N; i++) for(j=0; j<N; j++) g[i][j].t1=g[i][j].t2=INF; memset(node,0,sizeof(node)); for(i=1; i<=m; i++) { scanf("%s%s%d%d",s1,s2,&t1,&t2); x1=find(node,s1); x2=find(node,s2); g[x1][x2].t1=t1; g[x1][x2].t2=t2; } n=strlen(node+1); scanf("%s%s",s1,s2); V0=find(node,s1); V=find(node,s2); /* printf("%d\n",n); printf("%s\n",node+1); for(i=1; i<=n; i++) { for(j=1; j<=n; j++) printf("%d\\%d ",g[i][j].t1,g[i][j].t2); printf("\n"); } printf("%d %d\n",V0,V); */ return ; } int green_or_red(int t , int w) //0是红灯1是绿灯 { return ((t/w)%2) ; } void init() { int i,tmp; for(i=1; i<=n; i++) { cov[i]=0; //表示还没有找到i点的最短距离 path[i]=1; //记录路径 D[i]=g[V0][i].t1; if(g[V0][i].t1!=INF) //即到i点有通路 if(g[V0][i].t2!=0 && !green_or_red(D[i],g[V0][i].t2) ) D[i]+=g[V0][i].t2-D[i]%g[V0][i].t2; //红绿灯的时间不为0（否则会有除0错误），并且计算得到是红灯，要加上等待时间 } cov[V0]=1; //源点的最短距不用求 //for(i=1; i<=n; i++) //printf("%d\n",D[i]); return ; } void DIJ() { int nn,i,min,k,tmp,wait; for(nn=1; nn<n; nn++) //个数，还要覆盖其余n-1个点，即求出其余n-1个点的最短距 { min=INF; k=1; for(i=1; i<=n; i++) if(!cov[i])//扫描所有点，找到还没有被覆盖并且距离最短的点 if(D[i]<min) { min=D[i]; k=i; } cov[k]=1; for(i=1; i<=n; i++) if(!cov[i])//更新所有n个点的最短距离
{//g[k][i]+min < D[i] 原来的模板代码 if(g[k][i].t1!=INF) //存在通路k->i ,这样才会有红绿灯 { if(g[k][i].t2!=0 && !green_or_red(min+g[k][i].t1 , g[k][i].t2) ) //红绿灯时间不为0 { wait=g[k][i].t2-(min+g[k][i].t1)%g[k][i].t2; if(min+g[k][i].t1+wait < D[i]) { D[i]=min+g[k][i].t1+wait; path[i]=k; } } else //绿灯（包括了红绿灯时间为0和不为0但刚好遇到绿灯的情况），不用算等待时间 { if(min+g[k][i].t1 < D[i]) { D[i]=min+g[k][i].t1; path[i]=k; } } } } } return ; } void print_path(int i) { int j; if(i==V0) { printf("%d",i); return ; } print_path(path[i]); printf(" %d",i); return ; } void printfff() { int i; //for(i=1; i<=n; i++) //printf("D[%d]=%d\n",i,D[i]); printf("%d\n",D[V]); //print_path(V); } int main() { int T; scanf("%d",&T); while(T--) { input(); init(); DIJ(); printfff(); } return 0; }
代码中记录了路径，题目并没有要求只是顺便练习一下，输出函数那里也有打印路径的代码不过不需要就注释掉了