제출 #914159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
914159		andrei_iorgulescu	Robot (JOI21_ho_t4)	C++14	34 / 100	3058 ms	155852 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

ll inf = 1e18;

struct ura
{
    int x,y,culoare,pret;
};

vector<ura>muchii;
int n,m;
map<pair<int,int>,int>cul,cost;
set<int>culori[100005];
vector<ll>d[100005];
vector<vector<pair<pair<int,int>,ll>>>g[100005];
map<pair<int,int>,int>idkmap;
map<pair<int,int>,ll>sumcost;

void putedge(int x,int y)
{
    //cout << x << ' ' << y << endl;
    int c = cul[{x,y}];
    int pret = cost[{x,y}];
    ///(x,0) -> (y,0)
    ll cost1 = pret;
    ll cost2 = sumcost[{x,c}] - cost1;
    ll act_cost = min(cost1,cost2);
    g[x][0].push_back({{y,0},act_cost});
    //cout << "1" << endl;
    ///(x,0) -> (y,c)
    g[x][0].push_back({{y,idkmap[{y,c}]},0});
    //cout << "2" << endl;
    ///(x,c) -> (y,0)
    act_cost = sumcost[{x,c}] - cost1;
    g[x][idkmap[{x,c}]].push_back({{y,0},act_cost});
    //cout << "3" << endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x,y,culoare,pret;
        cin >> x >> y >> culoare >> pret;
        sumcost[{x,culoare}] += pret;
        sumcost[{y,culoare}] += pret;
        ura aux;
        aux.x = x;
        aux.y = y;
        aux.culoare = culoare;
        aux.pret = pret;
        muchii.push_back(aux);
        cul[{x,y}] = cul[{y,x}] = culoare;
        cost[{x,y}] = cost[{y,x}] = pret;
        culori[x].insert(culoare);
        culori[y].insert(culoare);
    }
    for (int i = 1; i <= n; i++)
    {
        d[i].resize(culori[i].size() + 1);
        //c[i].resize(culori[i].size() + 1);
        for (int j = 0; j <= culori[i].size(); j++)
            d[i][j] = inf;
        g[i].resize(culori[i].size() + 1);
        int jjj = 0;
        for (auto it : culori[i])
        {
            jjj++;
            //c[i][jjj] = it;
            idkmap[{i,it}] = jjj;
        }
    }
    for (auto it : muchii)
    {
        putedge(it.x,it.y);
        putedge(it.y,it.x);
    }
    priority_queue<pair<ll,pair<int,int>>>pq;
    pq.push({0,{1,0}});
    while (!pq.empty())
    {
        pair<int,int>nod = pq.top().second;
        ll timp = -pq.top().first;
        pq.pop();
        if (d[nod.first][nod.second] == inf)
        {
            d[nod.first][nod.second] = timp;
            if (nod.first == n and nod.second == 0)
                break;
            for (auto vecin : g[nod.first][nod.second])
            {
                pair<ll,pair<int,int>>de_bagat;
                de_bagat.first = -(timp + vecin.second);
                de_bagat.second = vecin.first;
                pq.push(de_bagat);
            }
        }
    }
    if (d[n][0] == inf)
        cout << -1;
    else
        cout << d[n][0];
    return 0;
}

/**
Stari: {nod,-1}, {nod,cul}, [nod,cul]
le definesc prin pereche (nod,-1 sau ceva intre 1 si m sau ceva intre 1 si 2m)
pentru nod, pot avea (nod,-1), (nod,c din culori[nod]) sau (nod, m + c din culori[nod])

Tranzitii:
(nod,-1) -> (vecin,-1) cost = min(toate muchiile adiacente cu nod de culoarea cul[{nod,vecin}] mai putin fix muchia {nod,vecin}, cost[{nod,vecin}])
(nod,-1) -> (vecin, cul[{nod,vecin}]) de cost 0
(nod,c) -> (vecin,-1) de cost toate muchiile adiacente cu nod de culoarea c mai putin fix muchia {nod,vecin}, conditie: cul[{nod,vecin}] = c

initial (1,-1) = 0
raspunsul este (n,-1)
**/

/**
graful asta are n + 2m noduri cel mult
(nod,c) pot sa pp ca are doar muchii de culoarea c
atunci numarul de muchii este 2m + 2m + 2m = 6m muchii
pe care dau un dijksta finut, iese N = n + 2m si M = 6m, iese MlogM + N
**/

/**
cum tin graful?
pai am o matrice de stari
la o linie am asa:
(nod,0) reprezinta (nod,-1)
(nod,1),(nod,2),...,(nod,k[nod]) reprezinta culorile din nod
**/

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:70:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for (int j = 0; j <= culori[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 34 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42