留个板子
2019 南昌网络赛B

题意

v个点，e条边（可能重边，无影响），救火英雄在s点，剩下的k个救援队在k个位置，现在要求救火英雄对所有点的最短路的最大值乘1/c与k个救援队对所有点的最短路，取最小值输出（救火英雄要输出没乘1/c之前的）

分析

我们直接跑两边dijstra就行了，第一遍正常跑，以s为源点，第二遍，建立一个超级源点连接k个救援队的位置，权值为0，在跑一边dijstra,最后在比较

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int V = 1000 + 100;
const int E = V * V / 2;
struct node 
{
    int next, to, w;
}edge[E << 1];
struct zz 
{
    int id;
    ll value;
    zz(int _id = 0, ll _value = 0) : id(_id), value(_value) {}
    bool operator < (const zz& a) const 
    {
        return value > a.value;
    }
};
bool vis[V];
int head[V], tot, v, e, s, k, c;
int kk[V];
ll dis[V];
void init()
{
    tot = 0;
    memset(head, -1, sizeof(head));
    memset(vis, false, sizeof(vis));
}
void add(int u, int v, int w)
{
    edge[tot].to = v;
    edge[tot].w = w;
    edge[tot].next = head[u];
    head[u] = tot ++;
}
void dijstra(int x)
{
    priority_queue <zz> q;
    memset(dis, 0x7f, sizeof(dis));
    dis[x] = 0;
    q.push(zz(x, 0));
    while(!q.empty())
    {
        zz tp = q.top();
        q.pop();
        int u = tp.id;
        if(vis[u])
            continue;
        vis[u] = true;
        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            int to = edge[i].to;
            ll w = edge[i].w;
            if(dis[to] > dis[u] + w)
            {
                dis[to] = dis[u] + w;
                q.push(zz(to, dis[to]));
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t --)
    {
        init();
        cin >> v >> e >> s >> k >> c;
        for(int i = 0; i < k; i ++)
            cin >> kk[i];
        for(int i = 1; i <= e; i ++)
        {
            int u, v, w;
            cin >> u >> v >> w;
            add(u, v, w);
            add(v, u, w);
        }
        dijstra(s);
        ll nu1 = 0, nu2 = 0;
        for(int i = 1; i <= v; i ++)
            nu1 = max(nu1, dis[i]);
        memset(vis, false, sizeof(vis));
        for(int i = 0; i < k; i ++)
        {
            add(0, kk[i], 0);
            add(kk[i], 0, 0);
        }
        dijstra(0);
        for(int i = 1; i <= v; i ++)
            nu2 = max(nu2, dis[i]);
        if(nu1 <= nu2 * c)
            cout << nu1 << endl;
        else 
            cout << nu2 << endl;
    }
}