\u5c31\u662f\u6700\u77ed\u8def\u3002\u3002\u6ca1\u6709\u4efb\u4f55\u96be\u70b9\u3002\u3002\u5c31\u662f\u6298\u78e8\u4f60\u548c\u4f60\u7684\u952e\u76d8\u7684\u3002\u3002
\u611f\u89c9\u6211\u5199\u7684\u5f88\u4e0d\u9519\u963f\u3002\u3002\u601d\u8def\u5f88\u6e05\u6670\u963f\u3002\u3002\uff08\u5c0f\u81ea\u604b\u4e00\u4e0b\u3002\u3002\u3002\uff09
\u8ddf\u6700\u77ed\u8def\u4e00\u6837\u7528D[X]\u8868\u793a\u5230X\u7684\u6700\u77ed\u8def\u3002\u3002
\u4eceX\u66f4\u65b0\u6709\u4e24\u79cd\u529e\u6cd5\u3002\u3002
\u4e00\u662f\u76f4\u63a5\u4e0a\uff08\u4e24\u8fb9\u989c\u8272\u8981same\uff09
\u4e8c\u662f\u7b49\u7b49\u4e0a\u3002\u3002\u3002\uff08\u4e5f\u53ef\u80fd\u7b49\u4e0d\u5230\u963f\u3002\u3002\uff09
\u76f4\u63a5\u4e0a\u81ea\u7136\u6ca1\u6709\u82b1\u5934\u3002\u3002\u7b49\u7b49\u4e0a\u5c31\u8ddf\u6ce1\u599e\u7684\u8fc2\u56de\u6218\u672f\u4e00\u6837\u3002\u3002
\u5f88\u590d\u6742\u963f\u3002\u3002\u5f88BT\u963f\u3002\u3002\u61d2\u5f97\u5199\u3002\u3002\u770b\u7a0b\u5e8f\u5427\u3002\u3002\u3002
\u6211\u4e00\u5f00\u59cb\u5c31\u5199\u4e86\u4e24\u4e2a\u51fd\u6570\u6765\u7b80\u5316\u601d\u7ef4\u3002\u3002\u5b9e\u9645\u4e0a\u8fd9\u4e24\u4e2a\u51fd\u6570\u4e5f\u4e0d\u662f\u90a3\u4e48\u597d\u5199\u7684\u3002\u3002
\u611f\u89c9\u8fd9\u4e24\u4e2a\u51fd\u6570\u505a\u4e86\u5f88\u591a\u91cd\u590d\u7684\u5de5\u4f5c\u963f\u3002\u3002\u4e0d\u8be5\u5206\u5f00\u963f\uff08\u4e0d\u8fc7\u61d2\u5f97\u6539\u4e86\uff09\u3002\u3002
\/\/important function
bool Colour(int n,int time)
{
if(time<Start[n]) return First[n];
time-=Start[n];
time%=(Dur[n][1]+Dur[n][0]);
if(time<Dur[n][ !First[n] ]) return !First[n];
return First[n];
}
int Next(int n,int time)
{
if(time<Start[n]) return Start[n]-time;
time-=Start[n];
time%=(Dur[n][1]+Dur[n][0]);
if(time<Dur[n][!First[n]]) return Dur[n][!First[n]]-time;
return Dur[n][0]+Dur[n][1]-time;
}
P.S\u8fd9\u660e\u660e\u662f\u4e2a\u7a20\u5bc6\u56fe\u6211\u5c45\u7136\u6c99\u8336\u5230\u4e9bHeap+Dij\u3002\u3002\u7ed3\u679c\u6162\u7684\u8981\u6b7b\u3002\u3002
Code\u3002\u3002
#include<iostream>
#include<string.h>
using namespace std;
\/\/main data
const int maxn=301;
const bool Blue=1,Purple=0;
const int inf=~0U>>1;
int Start[maxn],Dur[maxn][2],First[maxn];
\/\/important function
bool Colour(int n,int time)
{
if(time<Start[n]) return First[n];
time-=Start[n];
time%=(Dur[n][1]+Dur[n][0]);
if(time<Dur[n][ !First[n] ]) return !First[n];
return First[n];
}
int Next(int n,int time)
{
if(time<Start[n]) return Start[n]-time;
time-=Start[n];
time%=(Dur[n][1]+Dur[n][0]);
if(time<Dur[n][!First[n]]) return Dur[n][!First[n]]-time;
return Dur[n][0]+Dur[n][1]-time;
}
\/\/graph
int N,M;
int vs,vt;
struct edge
{
int t,c;
edge* next;
edge(int tt,int cc,edge* nn):t(tt),c(cc){next=nn;}
}*E[maxn];
inline void add(int s,int t,int c)
{
E[s]=new edge(t,c,E[s]);
E[t]=new edge(s,c,E[t]);
}
\/\/heap<\/p>\n
class heap
{
int Q[maxn],s,index[maxn],rdex[maxn];
void exch(int&x,int&y)
{int t=x;x=y;y=t;}
void swap(int x,int y)
{
exch(Q[x],Q[y]);exch(index[x],index[y]);
rdex[index[x]]=x;rdex[index[y]]=y;
}
void sink(int x)
{
int t=2*x;
while(t<=s)
{
if(t+1<=s&&Q[t+1]<Q[t]) t++;
if(Q[x]<Q[t]) break;
swap(x,t);x=t;t=2*x;
}
}
void swim(int x)
{
int t=x\/2;
while(t)
{
if(Q[t]>Q[x]) swap(x,t);
else break;
x=t;t=x\/2;
}
}
public:
void set(int n)
{
s=n;
for(int i=1;i<=s;i++)
{
index[i]=rdex[i]=i;
Q[i]=inf;
}
}
int Pop()
{
int t=index[1];
swap(1,s);s–;
sink(1);
return t;
}
void Lower(int x,int d)
{
Q[ rdex[x] ]=d;
swim( rdex[x] );
}
bool Empty(){return s==0;}
int operator[](int v)
{ return Q[ rdex[v] ]; }
};
void init()
{
cin>>vs>>vt;
cin>>N>>M;
for(int i=1;i<=N;i++)
{
char t;cin>>t;First[i]=(t==’B’);
cin>>Start[i]>>Dur[i][1]>>Dur[i][0];
}
for(int i=0;i<M;i++)
{
int s,t,c;cin>>s>>t>>c;
add(s,t,c);
}
}
int P[maxn];
heap H;
bool dijstra()
{
H.set(N);
H.Lower(vs,0);P[vs]=0;
bool Cal[maxn]={0};
while( !H.Empty() )
{
int v=H.Pop();
if(H[v]==inf) return false;
Cal[v]=true;
if(v==vt) return true;
int nextv=Next(v,H[v]);
bool colourv=Colour(v,H[v]);
for(edge*i=E[v];i;i=i->next)
if(!Cal[i->t])
{
int p=H[v]+i->c,w=i->t;
if( Colour(w,H[v]) != colourv )
{
int nextw=Next(w,H[v]);
bool colourw=Colour(w,H[v]);
p+=min(nextv,nextw);
if( nextw==nextv )
{
if(Dur[v][!colourv]!=Dur[w][!colourw])
p+=min(Dur[v][!colourv],Dur[w][!colourw]);
else
{
if(Dur[v][colourv]==Dur[w][colourw]) continue;
p+=min(Dur[v][colourv],Dur[w][colourw]);
}
}
}
if(p<H[w])
{
H.Lower(w,p);
P[w]=v;
}
}
}
return false;
}
int main()
{
init();
if(!dijstra() )
{
cout<<0<<endl;
return 0;
}
cout<<H[vt]<<endl;
int x=vt;
int ans[maxn],cnt=0;
while(P[x])
{
ans[cnt++]=x;
x=P[x];
}
ans[cnt++]=vs;
cout<<ans[cnt-1];
for(int i=cnt-2;i>=0;i–)
cout<<" "<<ans[i];
cout<<endl;
} <\/p>\n","protected":false},"excerpt":{"rendered":"
\u5c31\u662f\u6700\u77ed\u8def\u3002\u3002\u6ca1\u6709\u4efb\u4f55\u96be\u70b9\u3002\u3002\u5c31\u662f\u6298\u78e8\u4f60\u548c\u4f60\u7684\u952e\u76d8\u7684\u3002\u3002\u611f\u89c9\u6211\u5199\u7684\u5f88\u4e0d\u9519\u963f\u3002\u3002\u601d\u8def\u5f88\u6e05\u6670\u963f\u3002\u3002\uff08\u5c0f\u81ea\u604b\u4e00\u4e0b\u3002\u3002\u3002\uff09\u8ddf\u6700\u77ed\u8def\u4e00\u6837\u7528D[X]\u8868\u793a\u5230X\u7684\u6700\u77ed\u8def\u3002\u3002\u4eceX\u66f4\u65b0\u6709\u4e24\u79cd\u529e\u6cd5\u3002\u3002\u4e00\u662f\u76f4\u63a5\u4e0a\uff08\u4e24\u8fb9\u989c\u8272\u8981same\uff09\u4e8c\u662f\u7b49\u7b49\u4e0a\u3002\u3002\u3002\uff08\u4e5f\u53ef\u80fd\u7b49\u4e0d\u5230\u963f\u3002\u3002\uff09\u76f4\u63a5\u4e0a\u81ea\u7136\u6ca1\u6709\u82b1\u5934\u3002\u3002\u7b49\u7b49\u4e0a\u5c31\u8ddf\u6ce1\u599e\u7684\u8fc2\u56de\u6218\u672f\u4e00\u6837\u3002\u3002\u5f88\u590d\u6742\u963f\u3002\u3002\u5f88BT\u963f\u3002\u3002\u61d2\u5f97\u5199\u3002\u3002\u770b\u7a0b\u5e8f\u5427\u3002\u3002\u3002\u6211\u4e00\u5f00\u59cb\u5c31\u5199\u4e86\u4e24\u4e2a\u51fd\u6570\u6765\u7b80\u5316\u601d\u7ef4\u3002\u3002\u5b9e\u9645\u4e0a\u8fd9\u4e24\u4e2a\u51fd\u6570\u4e5f\u4e0d\u662f\u90a3\u4e48\u597d\u5199\u7684\u3002\u3002\u611f\u89c9\u8fd9\u4e24\u4e2a\u51fd\u6570\u505a\u4e86\u5f88\u591a\u91cd\u590d\u7684\u5de5\u4f5c\u963f\u3002\u3002\u4e0d\u8be5\u5206\u5f00\u963f\uff08\u4e0d\u8fc7\u61d2\u5f97\u6539\u4e86\uff09\u3002\u3002\/\/important functionbool Colour(int n,int time){if(time<Start[n]) return First[n];time-=Start[n];time%=(Dur[n][1]+Dur[n][0]);if(time<Dur[n][ !First[n] ]) return !First[n];return First[n];}int Next(int n,int time){if(time<Start[n]) return Start[n]-time;time-=Start[n];time%=(Dur[n][1]+Dur[n][0]);if(time<Dur[n][!First[n]]) return Dur[n][!First[n]]-time;return Dur[n][0]+Dur[n][1]-time;}P.S\u8fd9\u660e\u660e\u662f\u4e2a\u7a20\u5bc6\u56fe\u6211\u5c45\u7136\u6c99\u8336\u5230\u4e9bHeap+Dij\u3002\u3002\u7ed3\u679c\u6162\u7684\u8981\u6b7b\u3002\u3002Code\u3002\u3002#include<iostream>#include<string.h>using namespace std;\/\/main dataconst int maxn=301;const bool Blue=1,Purple=0;const int inf=~0U>>1;int Start[maxn],Dur[maxn][2],First[maxn];\/\/important functionbool Colour(int n,int time){if(time<Start[n]) return First[n];time-=Start[n];time%=(Dur[n][1]+Dur[n][0]);if(time<Dur[n][ !First[n] ]) return !First[n];return First[n];}int Next(int n,int time){if(time<Start[n]) return Start[n]-time;time-=Start[n];time%=(Dur[n][1]+Dur[n][0]);if(time<Dur[n][!First[n]]) return Dur[n][!First[n]]-time;return Dur[n][0]+Dur[n][1]-time;}\/\/graphint N,M;int vs,vt;struct edge{int t,c;edge* next;edge(int tt,int […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/649"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=649"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/649\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=649"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=649"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=649"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}