题解：P5060 旅行

· · 题解

题意简述

给定一张有向图，求从点 A 走到点 B 的一条路径，这条路径满足：

  1. 经过的边的权值总和是 P 的倍数。
  2. 在满足条件 1 的情况下，经过的边的权值总和最小。

题目分析

本题可以使用分层图最短路来解决。

仿照动态规划的思想，定义 f_{x,y} 表示从节点 A 到达节点 x，经过的边的权值总和 \bmod P 的值为 y 时，经过的边的权值总和最小是多少。

然后进行一遍 Dijkstra 算法，设当前考虑的节点为 a，当前经过的边的权值总和 \bmod P 的值为 b，扫描到一条通向点 c，权值为 d 的边，在满足“当前位于点 c，经过的边的权值总和 \bmod P 的值为 (b+d) \bmod P”这个状态没有被访问过的前提下，如果满足 f_{c,(b+d) \bmod P} > f_{a,b}+d，则使用 f_{a,b}+d 更新 f_{c,(b+d) \bmod P}。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){register int t1=0,t2=0;register char x=getchar();while(x<'0' ||x>'9'){if(x=='-') t2|=1;x=getchar();}while(x>='0' && x<='9'){t1=(t1<<1)+(t1<<3)+(x^48),x=getchar();}return t2?-t1:t1;}
inline void write(int x){register int sta[35],top=0;if(x<0) putchar('-'),x=-x;do{sta[top++]=x%10,x/=10;}while(x);while(top) putchar(sta[--top]+48);}
int n,m,p,s,t,f[50005][55],pre_now[50005][55],pre_use[50005][55];
bool vis[50005][55];
struct edge{
    int to,l;
};
vector<edge> v[50005];
struct node{
    int now,sum,use;
};
priority_queue<node> q;
bool operator <(const node &a,const node &b){
    return a.sum>b.sum;
}
vector<int> ans;
void get(int x,int y){//通过保存的路径信息得到具体地路径 
    if(!x) return;
    ans.push_back(x);
    get(pre_now[x][y],pre_use[x][y]);
}
signed main(){
    n=read();
    m=read();
    p=read();
    s=read();
    t=read();
    for(int i=1;i<=m;i++){
        int t1=read(),t2=read(),t3=read();
        v[t1].push_back({t2,t3});
    }
    memset(f,0x3f,sizeof(f));
    f[s][0]=0;
    q.push({s,0,0});
    while(!q.empty()){
        node temp=q.top();
        q.pop();
        if(vis[temp.now][temp.use]) continue;
        vis[temp.now][temp.use]=1;
        for(int i=0;i<v[temp.now].size();i++){
            int t1=v[temp.now][i].to,t2=v[temp.now][i].l;
            if(!vis[t1][(temp.use+t2)%p] && f[t1][(temp.use+t2)%p]>f[temp.now][temp.use]+t2){
                f[t1][(temp.use+t2)%p]=f[temp.now][temp.use]+t2;
                pre_now[t1][(temp.use+t2)%p]=temp.now;//保存路径信息 
                pre_use[t1][(temp.use+t2)%p]=temp.use;//同上 
                q.push({t1,f[t1][(temp.use+t2)%p],(temp.use+t2)%p});
            }
        }
    }
    if(f[t][0]==4557430888798830399) puts("jjc fails in travelling");//考虑无法完成的情况
    else{
        write(f[t][0]);
        putchar('\n');
        get(t,0);
        for(int i=ans.size()-1;i>0;i--){
            write(ans[i]);
            putchar('-');
            putchar('>');
        }
        write(ans[0]);
    }
    return 0;
}