n个点，m条边，给起点和终点，求起点到终点的最小花费，每个点都有两种状态，每个点的每种状态都有一个持续的时间，只有在某条边连接的两个点状态相同时这条边才可走。实际上就是一个带限制的最短路，每次松弛的时候，花费就是边的花费加上最少要等多长时间两个点的颜色会变成相同..如果永远无法相同，这条边就不能走了...思路很简单，时间的处理写起来比较恶心....
#include <iostream>#include <cstdio>#include <algorithm>#include <memory.h>#include <cmath>#include <string>#include <cstring>#include <queue>#include <stack>using namespace std;typedef long long ll;const int inf=(1<<28);const int maxn=330;int n,m,tt,p;int st,ed;struct EDGE{int v,w,next;}edge[30000];int g[maxn];int ne;struct Light{bool type;int res,t1,t2;}light[maxn];int pre[maxn];bool vis[maxn];int dis[maxn];int slove(int src){memset(vis,false,sizeof vis);memset(pre,0,sizeof pre);for (int i=0; i<=n; i++) dis[i]=inf;dis[src]=0;queue<int>q;q.push(src);vis[src]=true;while(!q.empty()){int u,v;int t1,t2;bool f1,f2;u=q.front();int now=dis[u];int cost=0;q.pop();vis[u]=false;for(int j=g[u]; j!=-1; j=edge[j].next){v=edge[j].v;cost=edge[j].w;t1=now-light[u].res;if (t1<0) f1=light[u].type,t1=light[u].res-now;else {t1=t1 % (light[u].t1+light[u].t2);if (!light[u].type){if (t1>=light[u].t2) f1=0,t1=light[u].t1+light[u].t2-t1;else f1=1,t1=light[u].t2-t1;}else{if (t1>=light[u].t1) f1=1,t1=light[u].t1+light[u].t2-t1;else f1=0,t1=light[u].t1-t1;}}t2=now-light[v].res;if (t2<0) f2=light[v].type,t2=light[v].res-now;else{t2=t2 % (light[v].t1+light[v].t2);if (!light[v].type){if (t2>=light[v].t2) f2=0,t2=light[v].t1+light[v].t2-t2;else f2=1,t2=light[v].t2-t2;}else{if (t2>=light[v].t1) f2=1,t2=light[v].t1+light[v].t2-t2;else f2=0,t2=light[v].t1-t2;}}if (f1==f2){if (dis[v]>cost+dis[u]){dis[v]=dis[u]+cost;pre[v]=u;if (!vis[v]){q.push(v);vis[v]=true;}}}else{bool ok=true;if (t1!=t2) cost+=min(t1,t2);else{f1^=1;f2^=1;cost+=t1;if (!f1) t1=light[u].t1;else t1=light[u].t2;if (!f2) t2=light[v].t1;else t2=light[v].t2;if (t1!=t2) cost+=min(t1,t2);else{f1^=1;f2^=1;cost+=t1;if (!f1) t1=light[u].t1;else t1=light[u].t2;if (!f2) t2=light[v].t1;else t2=light[v].t2;if (t1!=t2) cost+=min(t1,t2);else ok=false;}}if (ok){if (dis[v]>dis[u]+cost){dis[v]=dis[u]+cost;pre[v]=u;if (!vis[v]){q.push(v);vis[v]=true;}}}}}}return dis[ed];}void find(int u){if (u==0) return;find(pre[u]);if (u==st)printf("%d",u);else printf(" %d",u);}int main(){// freopen("in.txt","r",stdin);while(~scanf("%d%d",&st,&ed)){scanf("%d%d",&n,&m);char s[5];for (int i=1; i<=n; i++){scanf("%s",&s);light[i].type=(s[0]=='P');scanf("%d%d%d",&light[i].res,&light[i].t1,&light[i].t2);}ne=0;int x,y,z;memset(g,-1,sizeof g);for (int i=1; i<=m; i++){scanf("%d%d%d",&x,&y,&z);edge[ne].v=y;edge[ne].next=g[x];edge[ne].w=z;g[x]=ne;ne++;edge[ne].v=x;edge[ne].next=g[y];edge[ne].w=z;g[y]=ne;ne++;}int out=slove(st);if (out<inf){printf("%d\n",out);find(ed);printf("\n");}else puts("0");}return 0;}
