题面分析

比较经典的。

最短路本质上也是 dp，这种题就偏向于挖掘最短路的状态设计。

先考虑没有优惠券的情况，直接以所有投票城市为起点倒着建边来跑 Dijkstra，每次询问时看 $s$ 的值就好了。

现在加入优惠券，我们发现优惠券个数只有 5。于是我们把优惠券选择状态状态压缩，并在 Dijkstra 的状态里面加一维用来存它，转移很显然。

至于优惠券的价格，可以发现是不影响我们最短路结果的，只需要在每次询问时遍历到达 $s$ 的所有状态，根据优惠券使用情况加上其价格，再求所有状态中最小值就好了。

时间复杂度 $\mathcal{O}(n \log n + Q)$，带个 $2^5$ 的常数。

实际上由于 $Q$ 比较小，每次正着从 $s$ 跑一边似乎也能过？（复杂度 $\mathcal{O}(Qn \log n)$）

::::success[Code]

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define db double
#define fi first
#define se second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>

int rd()
{
    int x = 0,w = 1;
    char ch = 0;
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') w = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w;
}

const int N = 5e4 + 5;
const int inf = 1e18;
int n,m,k;
bool vote[N];
int dis[N][1 << 5];
bool vis[N][1 << 5];
vii adj[N];

struct node
{
    int u,dis,x;
    bool operator < (const node &x) const{ return dis > x.dis;}
};

void dij()
{
    for(int i = 0;i < n;i++) for(int j = 0;j < (1 << 5);j++) dis[i][j] = inf;
    priority_queue<node> q;
    for(int i = 0;i < n;i++) if(vote[i]) dis[i][0] = 0,q.push({i,0,0});
    while(!q.empty())
    {
        auto [u,d,x] = q.top();
        q.pop();
        if(vis[u][x]) continue;
        vis[u][x] = 1;
        for(auto [v,w] : adj[u])
        {
            if(dis[v][x] > d + w)
            {
                dis[v][x] = d + w;
                q.push({v,dis[v][x],x});
            }
            for(int i = 0;i < 5;i++)
            {
                if(!(x >> i & 1))
                {
                    int nx = x | (1 << i);
                    int cost = d + w * (9 - i) / 10;
                    if(dis[v][nx] > cost)
                    {
                        dis[v][nx] = cost;
                        q.push({v,dis[v][nx],nx});
                    }
                }
            }
        }
    }
}

int p[6];

void solve()
{
    int s = rd();
    for(int i = 0;i < 5;i++) p[i] = rd();
    int ans = inf;
    for(int x = 0;x < (1 << 5);x++)
    {
        int tmp = dis[s][x];
        for(int i = 0;i < 5;i++)
        {
            if(x >> i & 1)
            {
                if(p[i] == -1) { tmp = inf;break; }
                tmp += p[i];
            }
        }
        ans = min(ans,tmp);
    }
    cout << (ans == inf ? -1 : ans) << '\n';
}

signed main()
{
    n = rd(),m = rd(),k = rd();
    for(int i = 1;i <= k;i++) vote[rd()] = 1;
    for(int i = 1;i <= m;i++)
    {
        int u = rd(),v = rd(),w = rd();
        adj[v].push_back({u,w});
    }
    dij();
    int Q = rd();
    while(Q--) solve();
    return 0;
}