原题

提交记录

AT记录

#include <bits/stdc++.h>
#define int long long
#define pii pair<long long, long long>
#define endl "\n"

using namespace std;

int n, m, k, l, dis[100005], vis[100005], color[100005], sp[100005], ans[100005];
struct node
{
    int v, w;
};
vector<node> g[100005];
priority_queue<pii, vector<pii>, greater<pii> > que;

void dij(int p, int x)
{
    memset(vis, 0, sizeof(vis));
    while (!que.empty())
    {
        int h = que.top().second;
        que.pop();
        if(vis[h]) continue;
        vis[h] = 1;
        for(int i = 0; i < g[h].size(); i++)
        {
            int v = g[h][i].v;
            int w = g[h][i].w;
            if(dis[v] > dis[h] + w)
            {
                dis[v] = dis[h] + w;
                if((color[v] & (1ll << p)) != x)
                {
                    ans[v] = min(ans[v], dis[v]);
                }
                que.push({dis[v], v});
            }
        }
    }
    while(!que.empty())
    {
        que.pop();
    }
}

signed main()
{
    memset(ans, 127, sizeof(ans));
    cin >> n >> m >> k >> l;
    for(int i = 1; i <= n; i++)
    {
        cin >> color[i];
    }
    for(int i = 1; i <= l; i++)
    {
        cin >> sp[i];
    }
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    for(int i = 0; (1ll << i) <= k + 1; i++)
    {
        vector<int> zero, one;
        for(int j = 1; j <= l; j++)
        {
            if((color[sp[j]] & (1ll << i)) == 0)
            {
                zero.push_back(sp[j]);
            }
            else
            {
                one.push_back(sp[j]);
            }
        }
        // cout << "i == " << i << endl;
        // cout << "   zero: ";
        // for(int j = 0; j < zero.size(); j++)
        // {
        //     cout << zero[j] << " ";
        // }
        // cout << endl;

        // cout << "   one: ";
        // for(int j = 0; j < one.size(); j++)
        // {
        //     cout << one[j] << " ";
        // }
        // cout << endl;

        memset(dis, 127, sizeof(dis));
        for(int j = 0; j < zero.size(); j++)
        {
            dis[zero[j]] = 0;
            que.push({0, zero[j]});
        }
        dij(i, 0);

        memset(dis, 127, sizeof(dis));
        for(int j = 0; j < one.size(); j++)
        {
            dis[one[j]] = 0;
            que.push({0, one[j]});
        }
        dij(i, 1);
    }
    for (int i = 1; i <= n; i++)
    {
        cout << ((ans[i] == ans[0])? -1 : ans[i]) << " ";
    }

    return 0;
}