Luogu P5060 旅行 题解

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

#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');
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇