Poor Trip

Problem Statement

穷游中很重要的步骤是减少每晚的住宿费用。因此，想穷游的人到了北京、上海等大城市，往往就开始头疼了……

假设你作为一个穷游者，正准备从 S 城出发到 T 城，并且在中间经过的每个城市都停留一晚，体验城市的风土人情。但由于上面说到的因素，你自然不希望你的住宿费用太高，因此你希望规划一条路径，使得你停留的所有城市中的最贵的城市的住宿费用尽可能少。如果这样的路径不唯一，则选择路径中除到达最贵城市外总耗费时长最少的一条。

Input

输入第一行是两个正整数 $N,M$ ($1 \leq N \leq 1000, 1 \leq M \leq 3 \times 10^4$)，表示共有 $N$ 个城市，城市之间有 $M$ 条双向通行的通路连接。接下来首先是一行 $N$ 个整数 $C_i$ ($0 \leq C_i \leq 10^5$，$1 \leq i \leq N$)，第 $i$ 个数表示编号为 $i$ 的城市的住宿费用。注意城市编号从 1 开始。接下来有 $M$ 行描述通路，每行给出三个正整数，格式为 $V_1$ $V_2$ $T$ 其中 $V_1$ 和 $V_2$ 为通路两端城市的编号，$T$ 为通行此路需要的时间（$1 \leq T \leq 1000$）。最后是两个正整数 $S$ 和 $T$，表示出发城市和目标城市的编号。题目保证出发城市和目标城市的住宿费用一定是 0，且一定至少存在一条路径可以从 $S$ 到 $T$。

Output

输出两个整数，分别是你找到的满足条件的路径中最贵城市的住宿费用以及全程中除到达最贵城市外所需要耗费的最小时间。

Solving

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62


struct Node
{
    int node,hi,time; // hi : 途径的最贵住宿费用 time : 总花费
    bool operator<(const Node& obj) const 
    {
        // 注意，默认优先队列内的排序依据大的元素优先，所以实现小的元素优先弹出应该使用大于号
        if(hi != obj.hi) return hi > obj.hi; 
        return time > obj.time;
    }
};
struct Edge
{
    int to,next,w;
};
void solve()
{       
    int n,m;
    cin >> n >> m;
    vector<int> head(n+1);
    int eid = 0;
    vector<Edge> edge((m+1)<<1);
    auto addedge = [&](int u,int v,int w) -> void
    {
        edge[++eid] = {v,head[u],w};
        head[u] = eid;
    };
    vector<int> h(n+1);
    for(int i=1;i<=n;i++) cin >> h[i];
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin >> u >> v >> w;
        addedge(u,v,w);
        addedge(v,u,w);
    }
    int s,t;
    cin >> s >> t;
    vector<int> lo(n+1,INF); // s -> i 途径最贵酒店费用最小是多少
    vector<int> dis(n+1,INF);
    priority_queue<Node> q;
    q.push({s,0,0});    
    lo[s] = 0;
    dis[s] = 0; 
    while(!q.empty())
    {
        auto [u,hi,t] = q.top();
        q.pop();
        for(int i=head[u];i;i=edge[i].next)
        {
            int v = edge[i].to;
            int w = edge[i].w;
            // 如果途径最贵的酒店花费可以削减 或者 有着相同途径最贵酒店花费的情况下花费时间可以削减
            if(lo[v] > max(hi,h[v]) or (lo[v] == max(hi,h[v]) and dis[v] > t + w))
            {
                lo[v] = max(hi,h[v]);
                dis[v] = t + w;
                q.push({v,lo[v],dis[v]});
            }
        }
    }
    cout << lo[t] << ' ' << dis[t] << endl;
}