学步园

Your task is to find a path which takes the minimum time from a given source junction to a given destination junction for a vehicle when the traffic starts. In case more than one such path exists you are required to report only one of them.

The first line contains two numbers: The id-number of the source junction and the id-number of the destination junction. The second line contains two numbers: N, M. The following N lines contain information on N junctions.
The (i+2)'th line of the input file holds information about the junction i : C_i, r_iC, t_iB, t_iP where C_i is
either B for blue or P forpurple, indicating the initial color of the light at the junction i. Finally, the next M lines contain information on M roads. Each line is of the form: i, j, l_ij where i and j are
the id-numbers of the junctions which are connected by this road. 2 ≤ N ≤ 300 where N is the number of junctions. The junctions are identified by integers 1 through N. These numbers are called id-numbers. 1 ≤ M ≤ 14000 where M is
the number of roads. 1 ≤ l_ij ≤ 100 where l_ij is the time required to move from junction i to j using the road that connects i and j. 1 ≤ t_iC ≤
100 where t_iC is the duration of the color c for the light at the junction i. The index c is either 'B' for blue or 'P' for purple. 1 ≤ r_iC ≤ t_iC where r_iC is
the remaining time for the initial color c at junction i. 

If a path exists:

If a path does not exist:

sample input

sample output

1 4
4 5
B 2 16 99
P 6 32 13
P 2 87 4
P 38 96 49
1 2 4
1 3 40
2 3 75
2 4 76
3 4 77

127
1 2 4

-----------------

边权随着时间变化。可以证明dijkstra的贪心策略仍然适用。

所以只要计算出两点间的等待时间即可。

-----------------

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int maxn=1111;;
const int maxm=41111;
const int INF=0x3f3f3f3f;
int st,ed;
int n,m;
struct Node{
    char c[2];
    int r,tb,tp;
}a[maxn];

class Dijkstra{
private:
    struct EdgeNode{
        int to,w,next;
    };
    struct HeapNode{
        int u,d;
        HeapNode(int _u,int _d):u(_u),d(_d){}
        bool operator<(const HeapNode& rhs) const{
            return d>rhs.d;
        }
    };
    EdgeNode edges[maxm];
    int head[maxn],edge;
    int dis[maxn],pre[maxn];
    bool vis[maxn];
    priority_queue<HeapNode>que;
    void color(int time,int x,int &px,char cx[]){
        if (time<a[x].r){
            px=a[x].r-time;
            cx[0]=a[x].c[0];
            return;
        }
        int t=(time-a[x].r)%(a[x].tb+a[x].tp);
        if (a[x].c[0]=='B'&&t<a[x].tp){
            px=a[x].tp-t;
            cx[0]='P';
        }
        else if (a[x].c[0]=='P'&&t<a[x].tb){
            px=a[x].tb-t;
            cx[0]='B';
        }
        else{
            px=a[x].tb+a[x].tp-t;
            if (a[x].c[0]=='B') cx[0]='B';
            else cx[0]='P';
        }
    }
public:
    int getTime(int time,int x,int y,int num){
        if (num>3) return -1;
        int px,py;
        char cx[2],cy[2];
        color(time,x,px,cx);
        color(time,y,py,cy);
        if (cx[0]==cy[0]) return time;
        if (px==py) return getTime(time+px,x,y,num+1);
        time+=min(px,py);
        return time;
    }

    void addedge(int u,int v,int w){
        edges[edge].w=w,edges[edge].to=v,edges[edge].next=head[u],head[u]=edge++;
    }
    void init(){
        memset(head,-1,sizeof(head));
        edge=0;
    }
    int getDis(int i){
        return dis[i];
    }
    int getPre(int i){
        return pre[i];
    }
    void dijkstra(int s){
        while (!que.empty()) que.pop();
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        memset(pre,-1,sizeof(pre));
        dis[s]=0;
        que.push(HeapNode(s,0));
        while (!que.empty()){
            HeapNode top=que.top();
            que.pop();
            int u=top.u;
            if (vis[u]) continue;
            vis[u]=true;
            for (int i=head[u];i!=-1;i=edges[i].next){
                int v=edges[i].to;
                int w=edges[i].w;
                int time=getTime(dis[u],u,v,1);
                if (time==-1) continue;
                if (dis[v]>time+w){
                    dis[v]=time+w;
                    pre[v]=u;
                    que.push(HeapNode(v,dis[v]));
                }
            }
        }
    }
    void output(int u){
        if (pre[u]!=-1) output(pre[u]);
        else{
            printf("%d",u);
            return;
        }
        printf(" %d",u);
    }
}dij;

void init(){
    dij.init();
}

void input(){
    scanf("%d%d",&st,&ed);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        scanf("%s%d%d%d",a[i].c,&a[i].r,&a[i].tb,&a[i].tp);
    }
    for (int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        dij.addedge(u,v,w);
        dij.addedge(v,u,w);
    }
}

void solve(){
    dij.dijkstra(st);
    if (dij.getDis(ed)==INF) printf("0\n");
    else{
        printf("%d\n",dij.getDis(ed));
        dij.output(ed);
        printf("\n");
    }
}

int main()
{
    init();
    input();
    solve();
    return 0;
}

-----------------

-----------------