列表

详情

NC24615. [USACO 2011 Jan S]Traffic Lights

描述

Kenosha, the city nearest Farmer John, has M (1 <= M <= 14,000) roads conveniently numbered 1..M that connect N (2 <= N <= 300) junctions which are conveniently numbered 1..N. No two roads connect the same pair of junctions. No road connects a junction to itself. The integer travel time (1 <= <= 100) between junctions i and j is the same for both directions (i.e., = ).
Each junction has a single traffic light with two colors: blue or purple. The color of each light alternates periodically: blue for certain duration and then purple for another duration. Traffic is permitted to commence travel down the road between any two junctions, if and only if the lights at both junctions are the same color at the moment of departing from one junction for the other. The lights do not necessarily have to be the same on the whole trip down the road.
If a vehicle arrives at a junction just at the moment the lights switch it must consider the new colors of lights. Vehicles are allowed to wait at the junctions. You are given the city map which shows:
* The travel times  for all roads
* The durations of the two colors at junction i. (DB_i (1 <= DB_i <= 100) for the blue light and DP_i (1 <= DP_i <= 100) for the purple light)
* The initial color C_i of the light at junction i (a letter 'B' or 'P' with the obvious meaning) and the remaining time R_i (1 <= R_i <= 100) for this color to change
Find the minimum time one needs to get from a given source S (1 <= S <= N) to a given destination D (1 <= D <= N; D != S). 
Consider the map below with four junctions and five roads. FJ wants to travel from junction 1 to junction 4. The first light is blue; the rest are purple.                                     Init  Remg  Blue   Purple        4       76         Junction  Color Time  Cycle  Cycle >>[1B]===[2P]======          1        B    2     16      99     |   /          \         2        P    6     32      13   40|  /75          \        3        P    2     87       4     | /              \       4        P   38     96      49   [3P]===============[4P]>>            77 The minimum time is 127 utilizing the path 1-2-4.  Initially, the light at junction 1 is blue. Since the light at junction 2 is purple, vehicle waits at junction 1 for 2 seconds then travels 4 seconds to junction 2. At time 6, the light at junction 2 switches to blue whereas the light at junction 4 has 32 more seconds to switch to blue. However, after 32 seconds, the light at junction 2 switches to purple and the light at junction 4 switches to blue at the same time. So the vehicle needs to wait 13 seconds more for junction 2 to switch to blue then the lights have the same color and vehicle travels 76 seconds to the destination junction 4. The total time is 2+4+32+13+76=127 seconds.  Below is a more graphical presentation of this travel plan:                                                                                                        1    1    1    1    1    1              1    1    2    2    3    3    4    4    5    5    6    6    7    7    8    8    9    9    0    0    1    1    2    2    0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5..    -------------------------------------------------------------------------------------------------------------------------------- J1 BBBPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPBBBBBBBBBBBBBBBBPPPPPPPPPP J2 PPPPPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBPPPPPPPPPPPPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBPPPPPPPPPPPPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB J3 PPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBPPPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB J4 PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB FJ 1..>>>2............................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>4

输入描述

* Line 1: Two space-separated integers: S and D
* Line 2: Two space-separated integers: N and M
* Lines 3..N+2: Line i+2 line describes junction i with a character and three integers (all separated by a single space): C_i, R_i, DB_i, and DP_i
* Lines N+3..N+M+2: Line N+2+k describes road k with three integers: i, j, and

输出描述

* Line 1: One integer: the time taken by a minimum-time path from the source junction to the destination junction. If there is no path, output 0.

示例1

输入: 

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

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 10ms, 内存消耗: 1000K, 提交时间: 2020-02-29 20:45:26 

#include<bits/stdc++.h>
using namespace std;
constexpr int maxn = 300;
vector<pair<int, int>> G[maxn + 1];
int C[maxn + 1], R[maxn + 1], DT[2][maxn + 1];
int vis[maxn + 1];
int check(int t, int u){
    return t < R[u] ? C[u] : ((t - R[u]) % (DT[0][u] + DT[1][u]) < DT[C[u] ^ 1][u]) ^ C[u];
}
int check(int t, int u, int v){
    for(int x = t; x < t + 400; x += 1)
        if(check(x, u) == check(x, v))
            return x;
    return -1;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int S, D;
    cin >> S >> D;
    int N, M;
    cin >> N >> M;
    for(int i = 1; i <= N; i += 1){
        string s;
        cin >> s >> R[i] >> DT[0][i] >> DT[1][i];
        C[i] = s == "P";
    }
    for(int i = 1, u, v, w; i <= M; i += 1){
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({0, S});
    while(not q.empty()){
        auto p = q.top();
        q.pop();
        if(p.second == D){
            cout << p.first;
            return 0;
        }
        if(vis[p.second]) continue;
        vis[p.second] = true;
        for(auto f : G[p.second]){
            int w = check(p.first, p.second, f.first);
            if(w != -1) q.push({f.second + w, f.first});
        }
    }
    cout << 0;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 61ms, 内存消耗: 2384K, 提交时间: 2020-02-29 09:03:41 

#include<bits/stdc++.h>
#define maxn 50050
using namespace std;
int s,e,n,m,c[maxn],r[maxn],p1[maxn],p2[maxn];
struct data{int to,p,nt;}ll[maxn];
int tail,first[maxn];
void aa(int x,int y,int w){tail++;ll[tail].to=y;ll[tail].p=w;ll[tail].nt=first[x];first[x]=tail;}
int cc(int now,int x){if(now<r[x]) return c[x];int pig=(now-r[x])%(p1[x]+p2[x]);if(c[x]==1){if(pig-p2[x]>=0) return 1;return 2;}else{if(pig-p1[x]>=0) return 2;return 1;}}
struct node{int id,d;};
int dist[maxn],iq[305][100005];
queue<node> q;
void dd(){
    memset(dist,0x3f,sizeof(dist));
    dist[s]=0;
    q.push((node){s,0});
    iq[s][0]=1;
    while(!q.empty()){
        node t=q.front();q.pop();int x=t.id,now=t.d;
        iq[x][now]=0;if(now>100005) continue; 
        for(int i=first[x];i;i=ll[i].nt){
            int y=ll[i].to,w=ll[i].p;
            if(now+w<dist[y]){
                node pig;
                if(cc(now,x)==cc(now,y)){dist[y]=now+w;pig.id=y;pig.d=dist[y];}
                else pig.id=x,pig.d=now+1;
                if(!iq[pig.id][pig.d]){q.push(pig);iq[pig.id][pig.d]=1;}
            }
        }
    }
}
int main(){
    cin>>s>>e>>n>>m;
    int a,b,q;char pig;
    for(int i=1;i<=n;i++){cin>>pig;c[i]=(pig=='B')?1:2;cin>>r[i]>>p1[i]>>p2[i];}
    for(int i=1;i<=m;i++){cin>>a>>b>>q;aa(a,b,q);aa(b,a,q);}
    dd();
    if(dist[e]>200000000) puts("0");else printf("%d\n",dist[e]);
    return 0;
}

上一题

© 2024 nowcoder.com