UVa 12661 – Funny Car Racing [最短路]

点击打开vjudge题目链接

题意:在一个赛车比赛中,赛道有n哥交叉点和m条单向道路。每条道路都是周期性开关的,打开a秒,关闭b秒。比赛开始的时候,每条道路刚刚打开,你的赛车必须在道路打开的时候进入该道路,道路关闭之前离开。

练了这么长时间最短路了,这个还算简单,Dijkstra上的基础加了个分类讨论。这次比较爽,写完不Debug一遍AC,哈哈哈。

走每条边push的时候,都依赖于当前的时间,画画图分情况讨论下就可以了。感觉《挑战》上的模板更清晰,没用刘老师的模板。

C++代码:

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

struct Edge {
    int to, cost, a, b;
    Edge(int to, int cost, int a, int b) : to(to), cost(cost), a(a), b(b) { }
};

const int maxn = 305, inf = 0x3f3f3f3f;
int n, m, s, t, d[maxn], kase = 0;
vector<Edge> G[maxn];

void Dijkstra() {
    memset(d, inf, sizeof(d)); d[s] = 0;
    priority_queue<P, vector<P>, greater<P>> qu;
    qu.push(P(0, s));
    while (!qu.empty()) {
        P p = qu.top(); qu.pop();
        int v = p.second;
        if (d[v] < p.first) continue;
        for (Edge &e : G[v]) {
            int st = p.first;
            if (st % (e.a + e.b) > e.a || st % (e.a + e.b) + e.cost > e.a)
                st += e.a + e.b - st % (e.a + e.b);
            if(st % (e.a + e.b) + e.cost > e.a)
                continue;
            if (d[e.to] > st + e.cost) {
                d[e.to] = st + e.cost;
                qu.push(P(d[e.to], e.to));
            }
        }
    }
}

int main() {
    while (cin >> n >> m >> s >> t) {
        for (int i = 0; i < maxn; ++i) G[i].clear();
        for (int i = 0; i < m; ++i) {
            int u, v, a, b, t;
            cin >> u >> v >> a >> b >> t;
            G[u].push_back(Edge(v, t, a, b));
        }
        Dijkstra();
        printf("Case %d: %d\n", ++kase, d[t]);
    }
    return 0;
}

欢迎留言