题解：P7655 [BalticOI 1996] A FAST JOURNEY (Day 2)

· · 题解

题目大意

你每天最多开车 12 小时，道路方向奇偶天交替反转；晚上可以住店等第二天。

求从 A 到 B 的最短总耗时路线，并输出每一段走的路程、出发日期和耗时。

思路

设状态为当前在那个城市，今天旅行天数的奇偶性和当天走了多久。~为了好看~为了节省空间，我们把这个三元的状态压成一元。

然后在图上跑最短路，记录前驱并恢复路径然后输出每一段走过的路即可。

:::info[AC 代码]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,x,y,z) for(int i=x;i<=y;i+=z)
#define ROF(i,x,y,z) for(int i=x;i>=y;i-=z)
#define PII pair<int,int>
inline void rd(int &x){
    x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    x*=f;
}inline void wr(auto x,char end='\n'){
    if(x<0)putchar('-'),x=-x;
    char b[20];int len=0;
    if(x==0)b[++len]=0;
    while(x)b[++len]=x%10,x/=10;
    while(len)putchar(b[len--]+'0');
    putchar(end);
}const int N=2e2+10,M=2e4+10;
const int INF=0x3f3f3f3f3f3f3f3f,MAXS=N*2*13+10;
int n,k,A,B,S,T,eu[M],ev[M],ew[M],dis[MAXS],prv[MAXS],via[MAXS],vdir[MAXS],path[MAXS];
vector<vector<pair<int,int>>>g;
auto enc=[](int u,int p,int used){return (u*2+p)*13+used;};
signed main(){
    rd(A),rd(B),A--,B--;rd(n),rd(k);g.resize(n);FOR(i,0,k-1,1){
        int u,v,w;rd(u),rd(v),rd(w),u--,v--;
        eu[i]=u,ev[i]=v,ew[i]=w;
        g[u].push_back({v,i});g[v].push_back({u,i});
    }fill(dis,dis+MAXS,INF);fill(prv,prv+MAXS,-1);fill(via,via+MAXS,-1);fill(vdir,vdir+MAXS,-1);
    priority_queue<PII,vector<PII>,greater<PII>>pq;
    S=enc(A,1,0);dis[S]=0;pq.push({0,S});T=-1;
    while(!pq.empty()){
        auto [d,s]=pq.top();pq.pop();
        if(d>dis[s])continue;
        int used=s%13,t=s/13,p=t%2,u=t/2;
        if(u==B){T=s;break;}
        int nd=d+(24-used),ns=enc(u,1-p,0);
        if(nd<dis[ns]){dis[ns]=nd;prv[ns]=s;via[ns]=-1;vdir[ns]=-1;pq.push({nd,ns});}
        for(auto [v,eid]:g[u]){
            if(p==1){if(u!=eu[eid])continue;}
            else{if(u!=ev[eid])continue;}
            if(used+ew[eid]>12)continue;
            int ns=enc(v,p,used+ew[eid]),nd=d+ew[eid];
            if(nd<dis[ns]){dis[ns]=nd;prv[ns]=s;via[ns]=eid;vdir[ns]=(p==1)?0:1;pq.push({nd,ns});}
        }
    }if(T==-1)return 0;
    int plen=0,cur=T;while(cur!=S){path[plen++]=cur;cur=prv[cur];}
    for(int idx=plen-1;idx>=0;idx--){
        int s=path[idx];if(via[s]==-1)continue;
        int eid=via[s],dir=vdir[s],from,to;
        if(dir==0)from=eu[eid],to=ev[eid];
        else from=ev[eid],to=eu[eid];
        int pd=dis[prv[s]],day=pd/24+1;
        wr(from+1,' '),wr(to+1,' '),wr(day,' '),wr(ew[eid]);
    }return 0;
}

:::