Description

Hannah recently discovered her passion for baking pizzas, and decided to open a pizzeria in downtown Stockholm. She did this with the help of her sister, Holly, who was tasked with delivering the pizzas. Their pizzeria is an instant hit with the locals, but, sadly, the pizzeria keeps losing money. Hannah blames the guarantee they put forth when they advertised the pizzeria:

Do you have a craving for a delicious pizza? Do you want one right now? Order at Hannah's pizzeria and we will deliver the pizza to your door. If more than 20 minutes elapse from the time you place your order until you receive your Hannah's pizza, the pizza will be free of charge!

Even though Holly's delivery car can hold an arbitrary number of pizzas, she has not been able to keep up with the large number of orders placed, meaning they have had to give away a number of pizzas due to late deliveries.

Trying to figure out the best way to fix the situation, Hannah has now asked you to help her do some analysis of yesterday's orders. In particular, if Holly would have known the set of orders beforehand and used an optimal delivery strategy, what is the longest a customer would have had to wait from the time they placed their order until they received their pizza?

Hannah provides you with a map of the roads and road intersections of Stockholm. She also gives you the list of yesterday's orders: order i was placed at time si from road intersection ui, and the pizza for this order was out of the oven and ready to be picked up for delivery at time ti. Hannah is very strict about following the "first come, first served" principle: if order i was placed before order j (i.e. si < sj), then the pizza for order i will be out of the oven before the pizza for order j (i.e. ti < tj), and the pizza for order i must be delivered before the pizza for order j​.

Input

The first line of input contains two integers n and m (2 ≤ n ≤ 1 000, 1 ≤ m ≤ 5 000), where n is the number of road intersections in Stockholm and m is the number of roads. Then follow m lines, the i'th of which contains three integers ui, vi and di denoting that there is a bidirectional road between intersections ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi), and it takes Holly's delivery car di time units to cross this road in either direction (0 ≤ di ≤ 108). There is at most one road between any pair of intersections.

Then follows a line containing an integer k, the number of orders (1 ≤ k ≤ 1 000). Then follow k lines, the i'th of which contains three integers si, ui, ti denoting that an order was made at time si from road intersection ui (2 ≤ ui ≤ n), and that the order is ready for delivery at time ti (0 ≤ si ≤ ti ≤ 108). The orders are given in increasing order of when they were placed, i.e. si < sj and ti < tj for all 1 ≤ i < j ≤ k.

Hannah's pizzeria is located at road intersection 1, and Holly and her delivery car are stationed at the pizzeria at time 0​. It is possible to reach any road intersection from the pizzeria.

Output

Output a single integer denoting the longest time a customer has to wait from the time they place their order until the order is delivered, assuming that Holly uses a delivery schedule minimizing this value.

Sample Input

4 4
1 2 2
2 3 4
3 4 1
4 1 2
3
1 4 2
3 3 3
4 3 6
----------------------------
3 2
1 2 1
3 2 2
4
0 3 1
1 3 3
2 2 4
4 3 6

Sample Output

6
-----------------------
8

Hint

1--2--2
|    |
2    4
|    |
4--1--3

3: take pizzas 1, 2
5: deliver pizza 1 (4)
6: deliver pizza 2 (3)
9: take pizza 3
11: deliver pizza 3 (7)

6: take pizzas 1,2,3
8: deliver pizza 1 (7)
9: deliver pizza 2,3 (6,5)

2: take pizza 1
4: deliver pizza 1 (3)
6: take pizza 2,3
9: deliver pizza 2,3 (6,5)

Source

ncpc2018

NCPC2018 Delivery Delays

这个题目要冷静分析!!!

先分析一下题目给的条件，题目说的是一家披萨店送披萨，给你送披萨的地图，还有每一个订单的时间和送达的地点
还有就是披萨出锅的时间，题目要求先到先得，就是订单越靠前就必须先送。
题目中给你的订单时间和出锅时间严格增加，让你求客户等待的最长时间的最小值。

这个题目首先要用到dij，其次应该要用到二分求等待最长时间的最小值。这个就是求最后一个人就是k
收到披萨的时间就可以了。
然后还要一个dp数组来记录到每一个点最短的时间。

所以这个就可以分成三个部分
第一个：就是用dis数组存储任意两个点之间的距离，跑n次dij即可

第二个就是算dp数组，这个就是根据二分枚举的每一个x来考虑，
因为这个订单可以一起送也可以分开送，所以就模拟一下这个过程，
如果第i个订单和i+1个订单一起送，首先我们可以判定就是dp[i]不会变小，所以这个时候就只要
去更新dp[i+1]即可，
这个时候情况会很多，我们可以所有的一起送，也可以选一部分一起送，所以对于每一个i我们都要考虑它和后面的一起送
这种情况，这样表述的不是很清楚，不过一些小细节可以自己思考思考。

第三个就是二分了，这个就是去枚举x等待的最长时间

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <string>
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
ll n, m, k;
ll dp[1010];
ll dis[1010][1010];
struct node
{
    ll to, dist;
    node(ll to = 0, ll dist = 0) :to(to), dist(dist) {}
};
bool vis[1010];
vector<node>vec[1010];
struct heapnode
{
    ll u, d;
    heapnode(ll u = 0, ll d = 0) :u(u), d(d) {}
    bool operator<(const heapnode&a)const
    {
        return a.d < d;
    }
};

void dij(int s)
{
    priority_queue<heapnode>que;
    dis[s][s] = 0;
    que.push(heapnode(s, 0));

    while (!que.empty())
    {
        heapnode e = que.top();
        que.pop();
        int u = e.u;
        if (vis[u]) continue;
        vis[u] = 1;
        int len = vec[u].size();
        for (int i = 0; i < len; i++)
        {
            node x = vec[u][i];
            if (dis[s][x.to] > dis[s][u] + x.dist)
            {
                dis[s][x.to] = dis[s][u] + x.dist;
                que.push(heapnode(x.to, dis[s][x.to]));
            }
        }
    }
}
ll s[1010], u[1010], t[1010];
bool pj(ll x)
{
    for (int i = 1; i <= k; i++) dp[i] = inf;
    ll arrivetime, watetime, settime;
    for (int i = 1; i <= k; i++)
    {
        settime = max(t[i], dp[i - 1] + dis[1][u[i - 1]]);//出发时间 第一层循环表示第i个和之后的一起，和之前的分开
        arrivetime = settime + dis[1][u[i]];//到达时间
        watetime = arrivetime - s[i];//等待时间
        if (watetime > x) continue;
        dp[i] = min(dp[i], arrivetime);
        for (int j = i + 1; j <= k; j++)
        {
            if (settime >= t[j])
            {
                arrivetime = arrivetime + dis[u[j - 1]][u[j]];//如果settime>t[j]就代表不需要等就可以之间带上它除法，所以到达时间就只要加上从j-1到j即可
                watetime = max(arrivetime - s[j], watetime);//等待时间，如果到达时间减去s[j]>watetime，但是不可能就是这个，因为到第j-1个就等待了watetime的时间，所以这个只能更大
            }
            else
            {
                arrivetime = arrivetime + dis[u[j - 1]][u[j]] + t[j] - settime;
                watetime = max(arrivetime - s[j], watetime + t[j] - settime);
            }
            //接下来就要更新settime
            if (watetime > x) break;
            settime = max(settime, t[j]);
            dp[j] = min(dp[j], arrivetime);
        }
    }
    if (dp[k] == inf) return false;
    return true;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        vec[a].push_back(node(b, c));
        vec[b].push_back(node(a, c));
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++) dis[i][j] = inf;
    }
    for (int i = 1; i <= n; i++)
    {
        memset(vis, 0, sizeof(vis));
        dij(i);
    }
    cin >> k;
    for (int i = 1; i <= k; i++)
    {
        cin >> s[i] >> u[i] >> t[i];
    }
    dp[0] = 0, t[0] = 0, u[0] = 1;
    ll l = 0, r = 1e18;
    if (pj(0))
    {
        cout << 0 << endl;
        return 0;
    }
    while (l < r)
    {
        ll mid = (l + r) / 2;
        if (pj(mid))
        {
            r = mid;
            if (l + 1 == r) break;
        }
        else
        {
            l = mid;
            if (l + 1 == r) break;
        }
    }
    if (pj(l)) r = l;
    cout << r << endl;
    return 0;
}

/**********************************************************************
    Problem: 2252
    User: echozhou
    Language: C++
    Result: AC
    Time:732 ms
    Memory:10496 kb
**********************************************************************/