UVa12661 Funny Car Racing(Dijkstra)

本文主要是介绍UVa12661 Funny Car Racing(Dijkstra)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给定n个点，m条边，起始点s，目标点t，求从起点s到终点t的最短距离。已经道路上的边e是每隔 $e_a$ 秒开启，再隔 $e_b$ 秒关闭，通过时间为 $e_t$

思路

在计算边 $e_{uv}$ 从u到v的时间时，用 $d_u$ 表示到达u时的时间，如果 $(d_u \bmod (e_a+e_b)) + e_t < e_a$ ,则 $d_v = d_u + e_t$ ，否则 $d_v=d_u - (d_u \bmod(e_a+e_b)) + e_a + e_b + e_t$

代码

#include <bits/stdc++.h>using namespace std;#define _for(i, a, b) for(int i = (a); i < (b); i++)
#define _rep(i, a, b) for (int i = (a); i <= (b); i++)struct Edge
{int from, to, dist, open, close;
};struct HeapNode
{int u, d;bool operator<(const HeapNode& other) const{return d > other.d;}
};template <size_t SZV, int INF>
struct Dijkstra
{int n;bool done[SZV];vector<Edge> edges;vector<int> graph[SZV];int d[SZV];int p[SZV];void init(int n){this-> n = n;_for(i, 0, n) {graph[i].clear();}edges.clear();}void addEdge(int from, int to, int w, int open, int close){graph[from].push_back(static_cast<int>(edges.size()));edges.push_back((Edge){from, to, w, open, close});}void dijkstra(int s){priority_queue<HeapNode> pq;fill_n(done, n, false);fill_n(d, n, INF);d[s] = 0;pq.push({s, 0});while (!pq.empty()) {HeapNode curNode = pq.top();pq.pop();int u = curNode.u;if (done[u]) {continue;}done[u] = true;_for(i, 0, static_cast<int>(graph[u].size())) {Edge& edge = edges[graph[u][i]];int newDist = arrive(d[u], edge);if (newDist < d[edge.to]) {d[edge.to] = newDist;pq.push((HeapNode){edge.to, newDist});}}}}int arrive(int d, const Edge& edge){int k = d % (edge.open + edge.close);if (k + edge.dist <= edge.open) {return d + edge.dist;}return d - k + edge.open + edge.close + edge.dist;}
};void fastio()
{ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
}const int MAXN = 305;
const int INF = 1e6;static Dijkstra<MAXN, INT_MAX> solver;int main()
{fastio();#ifndef ONLINE_JUDGEifstream fin("f:\\OJ\\uva_in.txt");streambuf* back = cin.rdbuf(fin.rdbuf());#endifint kase = 1;int n, m, s, t;while (cin >> n >> m >> s >> t) {solver.init(n + 1);_for(i, 0, m) {int u, v, a, b, w;cin >> u >> v >> a >> b >> w;if (w > a) {continue;}solver.addEdge(u, v, w, a, b);}solver.dijkstra(s);cout << "Case " << kase++ << ": " << solver.d[t] << endl;}#ifndef ONLINE_JUDGEcin.rdbuf(back);#endifreturn 0;
}