Luogu P5060 旅行 题解

Luogu P5060 旅行 题解

Describe

题目链接

Solution

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

关于spfa，她死了

Code

代码语言：javascript复制

#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 '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');
}

ode 递归

0 人点赞