제출 #1151019

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151019		vicvic	Voting Cities (NOI22_votingcity)	C++20	0 / 100	153 ms	2696 KiB

Main

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <cstdint>
#include <queue>
#define int long long
using namespace std;
const int inf=1e18;
int n, e, k;
vector <pair <int, int>> vec[5005];
int voting[5005], price[10], dp[5005][(1 << 5)];
priority_queue <vector <int>, vector <vector <int>>, greater <vector <int>>> setul;
vector <int> v;
void dijkstra (int nod)
{
    for (int i=1;i<=n;i++)
    {
        for (int j=0;j<(1 << 5);j++)
        {
            dp[i][j]=inf;
        }
    }
    /// pret, nod, stare
    dp[nod][0]=0;
    setul.push ({0, nod, 0});
    while (!setul.empty())
    {
        auto chestie=setul.top();
        setul.pop();
        if (chestie[0]!=dp[chestie[1]][chestie[2]])
            continue;
        for (auto adj : vec[chestie[1]])
        {
            if (dp[adj.first][chestie[2]]>dp[chestie[1]][chestie[2]]+adj.second)
            {
                dp[adj.first][chestie[2]]=dp[chestie[1]][chestie[2]]+adj.second;
                setul.push ({dp[adj.first][chestie[2]], adj.first, chestie[2]});
            }
            for (int j=0;j<=4;j++)
            {
                int stare=chestie[2];
                if (!(stare & (1 << j)) && price[j]!=-1)
                {
                    int stare2=stare & (1 << j);
                    if (dp[adj.first][stare2]>dp[chestie[1]][chestie[2]]+adj.second-adj.second*(j+1)*10/100+price[j])
                    {
                        dp[adj.first][stare2]=dp[chestie[1]][chestie[2]]+adj.second-adj.second*(j+1)*10/100+price[j];
                        setul.push ({dp[adj.first][stare2], adj.first, stare2});
                    }
                }
            }
        }
    }
}
int32_t main ()
{
    ios :: sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> n >> e >> k;
    for (int i=1;i<=k;i++)
    {
        int x;
        cin >> x;
        voting[x]=1;
        v.push_back (x);
    }
    for (int i=1;i<=e;i++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        vec[x].push_back ({y, c});
        vec[y].push_back ({x, c});
    }
    int q;
    cin >> q;
    while (q--)
    {
        int x;
        cin >> x;
        for (int i=0;i<=4;i++)
        {
            cin >> price[i];
        }
        dijkstra (x);
        int mn=inf;
        for (int msk=0;msk<(1 << 5);msk++)
        {
            bool ok=1;
            for (int j=0;j<=4;j++)
            {
                if ((msk & (1 << j)) && price[j]==-1)
                {
                    ok=0;
                }
            }
            if (!ok)
                continue;
            for (auto voting : v)
            {
                mn=min (mn, dp[voting][msk]);
            }
        }
        cout << (mn==inf?-1:mn) << "\n";
    }
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 10
• Subtask 7: 0 / 15
• Subtask 8: 0 / 50