旅行 题解

可以看出题意是求两点间最短的路径且是 $P$ 的倍数，应该有一点难度。 看到数据范围可以发现对于第二个子任务直接跑最短路就可以了 对于整道题能不能用最短路算法通过呢？ 答案是肯定的，对最短路算法本身进行一定调整即可解决本题 没有负权，因此我们使用堆优化 $dijkstra$ 算法，出题人卡了 $spfa$ ~~(不知道成功没有)~~ 使每一个点具有 $P$ 个意义，$dis[u][k]$表示到达 $u$ 点最短的路径满足模 $P$ 的余数为 $k$ ，则最终答案在 $dis[B][0]$ ，而在将点压堆时也要讲每一个意义独立开来，松弛时也要注意松弛对象只是一个点的一个意义而非整个点，想到这里，基本上就没什么问题了。时间复杂度 $O(N*P*log_2N)$ 接下来只需要记录路径，我采用的是记录前继的方法，注意 $dis$ 数组的初值 温馨提示：最好使用快读，最好不要使用优先队列代替手写堆。 $Code:$ ``` #include<iostream> #include<cstdio> #include<cstring> #include<cctype> using namespace std; struct edge { int to,next; long long w; }a[400010]; int head[50010],num,n,m,p,A,B,tempu,tempv,tot,pre[50010][50]; long long tempw,dis[50010][50],disp[50010][50];//disp 即dis_pre bool exist[50][50010]; pair<long long,int> heap[50010*50]; inline void add(int,int,long long); inline int read(); inline void dijkstra(); void print(int,int); int main() { n=read(),m=read(),p=read(),A=read(),B=read(); for(register int i=1;i<=m;i++) { tempu=read(),tempv=read(),tempw=read(); add(tempu,tempv,tempw); } dijkstra(); if(dis[B][0]==dis[0][0]) { printf("jjc fails in travelling"); return 0; } printf("%lld\n",dis[B][0]); print(B,0); printf("%d",B); return 0; } inline void add(int u,int v,long long w) { a[++num].to=v; a[num].w=w; a[num].next=head[u]; head[u]=num; } inline int read() { register int s=0; register char c=getchar(); while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') s=s*10+c-'0',c=getchar(); return s; } inline void Pop() { heap[1]=heap[tot--]; register int p=1,s; while(p*2<=tot) { s=p*2; if(s<tot&&heap[s+1]<heap[s]) s++; if(heap[s]<heap[p]) swap(heap[s],heap[p]),p=s; else break; } } inline void Push(pair<long long,int> d) { heap[++tot]=d; register int p=tot; while(p>1) { if(heap[p/2]>heap[p]) swap(heap[p/2],heap[p]),p/=2; else break; } } inline void dijkstra() { int k; long long fd,td; memset(dis,127,sizeof(dis)); dis[A][0]=0; heap[++tot]=make_pair(0ll,A); while(tot) { fd=heap[1].first,k=heap[1].second; Pop(); if(fd%p==0&&k==B) return; exist[fd%p][k]=true; for(register int i=head[k];i;i=a[i].next) { td=dis[k][fd%p]+a[i].w; if(td<dis[a[i].to][td%p]) { pre[a[i].to][td%p]=k; disp[a[i].to][td%p]=fd%p; dis[a[i].to][td%p]=td; if(!exist[td%p][a[i].to]) Push(make_pair(td,a[i].to)); } } } } void print(int x,int y) { if(!pre[x][y]) return; print(pre[x][y],disp[x][y]); printf("%d->",pre[x][y]); } ```