Submission #638745

#	Time	Username	Problem	Language	Result	Execution time	Memory
638745		danikoynov	Robot (JOI21_ho_t4)	C++14	0 / 100	2 ms	1876 KiB

Main

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

using namespace std;
typedef long long ll;

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

    edge(int _bef = 0, int _ver = 0, ll _len = 0, int _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 int maxn = 2010;
const ll inf = 1e18;

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

void djikstra(int v)
{
    for (int i = 1; i <= n; i ++)
        for (int 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();
        if (cur.len <= dp[cur.ver][cur.bef])
            if (!used[cur.ver][cur.bef])
            {
                used[cur.ver][cur.bef] = 0;
                if (cur.bef != cur.ver)
                {
                    cnt[cur.ver][cur.col] --;
                    sum[cur.ver][cur.col] -= cur.pr;
                }

                for (int 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.ver] > nb.len)
                        {
                            dp[nb.ver][nb.ver] = nb.len;
                            pq.push(nb);
                        }

                        nb.len -= nb.pr;
                        nb.len += cnt[cur.ver][cur.col] - nb.pr;
                        nb.bef = nb.ver;

                        if (cur.bef != cur.ver)
                        {
                            cnt[cur.ver][cur.col] ++;
                            sum[cur.ver][cur.col] += cur.pr;
                        }
                    }
                    else
                    {
                        nb.bef = nb.ver;
                        if (dp[nb.ver][nb.ver] > nb.len)
                        {
                            dp[nb.ver][nb.ver] = 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 (int i = 1; i <= m; i ++)
    {
        int 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 (int i = 1; i <= n; i ++)
        ans = min(ans, dp[n][i]);

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

int main()
{
    solve();
    return 0;
}

Compilation message (stderr)

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

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