Submission #639024

#	Time	Username	Problem	Language	Result	Execution time	Memory
639024		danikoynov	Robot (JOI21_ho_t4)	C++14	100 / 100	1716 ms	162444 KiB

Main

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;


struct edge
{
    int ver;
    ll len;

    edge(int _ver = 0, ll _len = 0)
    {
        ver = _ver;
        len = _len;
    }

    bool operator < (const edge &e) const
    {
        return len > e.len;
    }
};


const int maxn = 2e6 + 10;

int n, m, nxt;
map < pair < int, int >, int > mp;
map < pair < int, int >, ll > sum;
vector < edge > g[maxn];

int mp_idx(int v, int c)
{
    if (mp.find(make_pair(v, c)) == mp.end())
        mp[make_pair(v, c)] = ++ nxt;
    return mp[make_pair(v, c)];
}

struct road
{
    int v, u, c, p;

    road(int _v = 0, int _u = 0, int _c = 0, int _p = 0)
    {
        v = _v;
        u = _u;
        c = _c;
        p = _p;
    }
}r[maxn];

const ll inf = 1e18;
ll d[maxn];
int used[maxn];

void add_edge(int v, edge e)
{
    g[v].push_back(e);
    ///cout << v << " " << e.ver << " " << e.len << endl;
}
void solve()
{
    cin >> n >> m;
    nxt = n;
    for (int i = 1; i <= m; i ++)
    {
        int v, u, c, p;
        cin >> v >> u >> c >> p;
        r[i] = road(v, u, c, p);
        for (int t = 0; t < 2; t ++)
        {
            swap(v, u);
            ///g[v].push_back(edge(u, p));
            add_edge(v, edge(u, p));
            add_edge(v, edge(mp_idx(u, c), 0));
            ///g[v].push_back(edge(mp_idx(u, c), 0));

            ///cout << "to_add " << v << " " << c << " " << p << endl;
            sum[make_pair(v, c)] += p;
        }
    }

    map < pair < int, int >, int > :: iterator it;
    for (int i = 1; i <= m; i ++)
    {      int v = r[i].v, u = r[i].u, c = r[i].c, p = r[i].p;
        for (int t = 0; t < 2; t ++)
        {
           swap(v, u);
           add_edge(v, edge(u, sum[make_pair(v, c)] - p));
           add_edge(mp_idx(v, c), edge(u, sum[make_pair(v, c)] - p));
        }
    }
    /**for (it = mp.begin(); it != mp.end(); it ++)
    {
        pair < int, int > cur = it -> first;
        for (int j = 0; j < g[cur.first].size(); j ++)
        {
            int ver = g[cur.first][j].ver;
            if (ver <= n)
            {
                ///g[mp_idx(cur.first, cur.second)].push_back(edge(ver, sum[cur] - g[cur.first][j].len));
                cout << cur.first << " :: " << cur.second << " :: " << sum[cur] << " " << g[cur.first][j].len << endl;
                add_edge(mp_idx(cur.first, cur.second), edge(ver, sum[cur] - g[cur.first][j].len));
            }
        }
    }*/

    for (int i = 1; i <= m; i ++)
    {
        int v = r[i].v, u = r[i].u, c = r[i].c, p = r[i].p;
        for (int t = 0; t < 2; t ++)
        {
            swap(v, u);
            if (sum[make_pair(v, c)] == p)
            {
                ///g[v].push_back(edge(u, 0));
                add_edge(v, edge(u, 0));

            }
        }
    }

    for (int i = 1; i <= nxt; i ++)
        d[i] = inf;
    priority_queue < edge > pq;
    pq.push(edge(1, 0));
    d[1] = 0;
    while(!pq.empty())
    {
        edge e = pq.top();
        pq.pop();
        if (d[e.ver] >= e.len)
            if (!used[e.ver])
        {
            used[e.ver] = 1;
            for (int j = 0; j < g[e.ver].size(); j ++)
            {
                edge nb =  g[e.ver][j];
                nb.len += e.len;
                if (nb.len < d[nb.ver])
                {
                    d[nb.ver] = nb.len;
                    pq.push(nb);
                }
            }
        }
    }

    if (d[n] == inf)
        cout << -1 << endl;
    else
        cout << d[n] << endl;

}

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int main()
{
    ///freopen("input.txt", "r", stdin);
    speed();
    solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:137:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |             for (int j = 0; j < g[e.ver].size(); j ++)
      |                             ~~^~~~~~~~~~~~~~~~~

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