就是最短路。。没有任何难点。。就是折磨你和你的键盘的。。
感觉我写的很不错阿。。思路很清晰阿。。（小自恋一下。。。）
跟最短路一样用D[X]表示到X的最短路。。
从X更新有两种办法。。
一是直接上（两边颜色要same）
二是等等上。。。（也可能等不到阿。。）
直接上自然没有花头。。等等上就跟泡妞的迂回战术一样。。
很复杂阿。。很BT阿。。懒得写。。看程序吧。。。
我一开始就写了两个函数来简化思维。。实际上这两个函数也不是那么好写的。。
感觉这两个函数做了很多重复的工作阿。。不该分开阿（不过懒得改了）。。
//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这明明是个稠密图我居然沙茶到些Heap+Dij。。结果慢的要死。。
Code。。
#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
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;
}