Luogu P5060 旅行 题解

(Updated: )
oi
,

Describe

题目链接

给定一个 $N$ 个点， $M$ 条边的有向图，求从 $A$ 到 $B$ 的路径上边权和是 $P$ 的倍数的最短路径的长度及路径。 对于所有数据，$2\leq N \leq$$ 5\times $${10}^{4}$$,M\leq$$ 2 \times {10}^5$$ , 1\leq P $$\leq 50$。

Solution

设$dis[i][j]$表示从起点出发走到$i$的路径边权和$\% P=j$的最小值。 那么跑一次$Dijikstra$即可。 注意转移$dis[to][v+w[i]]=dis[u][v]+w[i]$。 保存路径可以记录根节点最后递归输出。 由于此题出题人不是特别友好，所以此题卡$spfa$，本人亲测$spfa$只有$80pts$。

关于spfa，她死了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
#define int long long //注意此题数据范围要开long long
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)//fread快读
inline int read(){int res=0,f=1;char ch=getchar();while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();return res*f;}
inline void write(int x){if(x<0) putchar('-'),x=-x;if(x<10) putchar(x+'0');else write(x/10),putchar(x%10+'0');}
int n,m,p,s,t,fir[50010],nxt[200010],son[200010],w[200010],tot,dis[50010][60],vis[50010][60],pre[50010][60][3],inf;
inline void add(int x,int y,int z){++tot;nxt[tot]=fir[x];fir[x]=tot;son[tot]=y;w[tot]=z;}
struct node{int id,val,note;bool operator < (const node &x) const{return val>x.val;}};
inline node make(int x,int y,int z){node pp;pp.id=x,pp.val=y,pp.note=z;return pp;}
priority_queue<node> q;
inline void dij(){
    while(!q.empty()) q.pop();//清空队列是个好习惯
    dis[s][0]=0;
    q.push(make(s,0,0));
    while(!q.empty()){
        node u=q.top();q.pop();
        if(vis[u.id][u.note]) continue ;
        vis[u.id][u.note]=1;
        for(int to,i=fir[u.id];i;i=nxt[i]){
            to=son[i];
            if(!vis[to][(u.note+w[i])%p]&&dis[to][(u.note+w[i])%p]>dis[u.id][u.note]+w[i]){
                dis[to][(u.note+w[i])%p]=dis[u.id][u.note]+w[i];
                pre[to][(u.note+w[i])%p][0]=u.id;//记录路径
                pre[to][(u.note+w[i])%p][1]=u.note;
                q.push(make(to,dis[to][(u.note+w[i])%p],(u.note+w[i])%p));
            }
        }
    }
}
inline void print(int x,int note,int fir){//递归输出路径
    if(!x) return ;
    print(pre[x][note][0],pre[x][note][1],1);
    write(x);
    if(!fir) return ;//判断不输出第一个->
    putchar('-');putchar('>');
}
signed main(){
    n=read(),m=read(),p=read(),s=read(),t=read();
    for(int x,y,z,i=1;i<=m;i++) x=read(),y=read(),z=read(),add(x,y,z);//有向图
    memset(dis,63,sizeof(dis));inf=dis[0][0];//清零
    dij();
    if(dis[t][0]==inf) puts("jjc fails in travelling");
    else write(dis[t][0]),putchar('\n'),print(t,0,0),putchar('\n');
}