UVa12661 Funny Car Racing (Dijkstra)

Question meaning

Given n points, m edges, starting point s, and target point t, find the shortest distance from starting point s to end point t. Already the edge e on the road is every

e

a

e_a

ea? seconds to turn on, and then wait

e

b

e_b

eb seconds to close, passing time is

e

t

e_t

et?

Ideas

On the calculation side

e

u

v

e_{uv}

euv? the time from u to v, use

d

u

d_u

du? represents the time when u is reached, if

(

d

u

?

m

o

d

?

(

e

a

+

e

b

)

)

+

e

t

< e a (d_u \bmod (e_a + e_b)) + e_t < e_a (du?mod(ea? + eb?)) + et?

Code

#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;
};

structHeapNode
{<!-- -->
    int u, d;

    bool operator<(const HeapNode & amp; 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 & amp; 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_JUDGE
        ifstream fin("f:\OJ\\uva_in.txt");
        streambuf* back = cin.rdbuf(fin.rdbuf());
    #endif

    int 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_JUDGE
        cin.rdbuf(back);
    #endif

    return 0;
}