Submission #638754

#	Time	Username	Problem	Language	Result	Execution time	Memory
638754		danikoynov	Robot (JOI21_ho_t4)	C++14	34 / 100	3038 ms	2097152 KiB

Main

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

using namespace std;
typedef long long ll;

struct edge
{
    ll bef, ver, col;
    ll len, pr;

    edge(ll _bef = 0, ll _ver = 0, ll _len = 0, ll _col = 0, ll _pr = 0)
    {
        bef = _bef;
        ver = _ver;
        len = _len;
        col = _col;
        pr = _pr;
    }

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

const ll maxn = 2e5 + 10;
const ll inf = 1e18;

ll n, m;
//ll dp[maxn][maxn], sum[maxn][maxn];
unordered_map < ll, ll > dp[maxn], sum[maxn], used[maxn], cnt[maxn];
//ll used[maxn][maxn], cnt[maxn][maxn];
vector < edge > g[maxn];

void djikstra(ll v)
{
    for (ll i = 1; i <= n; i ++)
        for (ll j = 1; j <= n; j ++)
            dp[i][j] = inf;

    priority_queue < edge > pq;
    pq.push(edge(v, v, 0, 0, 0));
    dp[v][v] = 0;
    while(!pq.empty())
    {
        edge cur = pq.top();
        pq.pop();
        ///cout << cur.ver << " " << cur.bef << " " << cur.len << endl;
        if (cur.len <= dp[cur.ver][cur.bef])
            if (!used[cur.ver][cur.bef])
            {
                used[cur.ver][cur.bef] = 1;
                if (cur.bef != cur.ver)
                {
                    cnt[cur.ver][cur.col] --;
                    sum[cur.ver][cur.col] -= cur.pr;
                }

                for (ll i = 0; i < g[cur.ver].size(); i ++)
                {
                    edge nb = g[cur.ver][i];
                    nb.len += cur.len;
                    if (cnt[cur.ver][nb.col] > 1 && nb.ver != cur.bef)
                    {
                        nb.len += nb.pr;
                        if (dp[nb.ver][nb.bef] > nb.len)
                        {
                            dp[nb.ver][nb.bef] = nb.len;
                            pq.push(nb);
                        }

                        nb.len -= nb.pr;
                        nb.len += sum[cur.ver][nb.col] - nb.pr;
                        nb.bef = nb.ver;
                        ///cout << nb.len << " " << nb.ver << " " << endl;
                        if (dp[nb.ver][nb.bef] > nb.len)
                        {
                            dp[nb.ver][nb.bef] = nb.len;
                            pq.push(nb);
                        }
                    }
                    else
                    {
                        nb.bef = nb.ver;
                        if (dp[nb.ver][nb.bef] > nb.len)
                        {
                            dp[nb.ver][nb.bef] = nb.len;
                            pq.push(nb);
                        }
                    }
                }
                if (cur.bef != cur.ver)
                {
                    cnt[cur.ver][cur.col] ++;
                    sum[cur.ver][cur.col] += cur.pr;
                }
            }
    }
}
void solve()
{
    cin >> n >> m;
    for (ll i = 1; i <= m; i ++)
    {
        ll v, u, c, p;
        cin >> v >> u >> c >> p;
        cnt[v][c] ++;
        cnt[u][c] ++;
        sum[v][c] += p;
        sum[u][c] += p;
        g[v].push_back(edge(v, u, 0, c, p));
        g[u].push_back(edge(u, v, 0, c, p));
    }

    djikstra(1);
    ll ans = inf;
    for (ll i = 1; i <= n; i ++)
        ans = min(ans, dp[n][i]);

    if (ans == inf)
        cout << -1 << endl;
    else
        cout << ans << endl;
}


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

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

Compilation message (stderr)

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

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