Submission #872091

#	Time	Username	Problem	Language	Result	Execution time	Memory
872091		abysmal	Robot (JOI21_ho_t4)	C++14	34 / 100	1059 ms	2097152 KiB

Main

#include<iostream>
#include<stdio.h>
#include<stdint.h>
#include<vector>
#include<algorithm>
#include<utility>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<string>
#include<assert.h>
#include<math.h>
#include<chrono>
#include<random>
#include<bitset>

using namespace std;

const int64_t INF = (int64_t) 1e18 + 5;
const int64_t mINF = (int64_t) 1e6 + 5;
const int64_t MOD = (int64_t) 1e9 + 9;
const int nbit = 30;
const int ndig = 10;
const int nchar = 26;
const int p1 = 31;
const int p2 = 69420;
const int D = 4;
int dr[D] = {0, 1, 0, -1};
int dc[D] = {1, 0, -1, 0};
// 0 right // 1 down // 2 left // 3 up

struct Node
{
    int u;
    int c;
    int64_t w;

    Node(int u_, int c_, int64_t w_) : u(u_), c(c_), w(w_) {}

    bool operator < (const Node& o) const
    {
        return w > o.w;
    }
};

struct Edge
{
    int v;
    int c;
    int w;

    Edge(int v_, int c_, int w_) : v(v_), c(c_), w(w_) {}
};

struct Solution
{
    int n;
    int m;
    vector<vector<Edge> > adj;
    vector<map<int, int64_t> > mp;
    vector<vector<int64_t> > dis;
    Solution() {}

    void solve()
    {
        cin >> n >> m;

        mp.resize(n);
        adj.resize(n);
        for(int i = 0; i < m; i++)
        {
            int u; int v;
            int c; int w;
            cin >> u >> v >> c >> w;
            u--; v--;

            mp[u][c] += w; mp[v][c] += w;
            adj[u].push_back(Edge(v, c, w));
            adj[v].push_back(Edge(u, c, w));
        }

        dis.resize(n, vector<int64_t>(m + 1, INF));
        Dijkstra();

        if(dis[n - 1][0] == INF) cout << "-1\n";
        else cout << dis[n - 1][0] << "\n";
    }

    void Dijkstra(int s = 0)
    {
        priority_queue<Node> pq;
        pq.push(Node(s, 0, 0));
        dis[s][0] = 0;

        while(!pq.empty())
        {
            Node x = pq.top();
            pq.pop();

            int u = x.u;
            int c = x.c;
            int64_t w = x.w;

            if(dis[u][c] != w) continue;
            for(int i = 0; i < (int) adj[u].size(); i++)
            {
                Edge e = adj[u][i];
                int v = e.v;

                if(c != 0)
                {
                    if(e.c == c && dis[v][0] > w + mp[u][e.c] - e.w)
                    {
                        dis[v][0] = w + mp[u][e.c] - e.w;
                        pq.push(Node(v, 0, w + mp[u][e.c] - e.w));
                    }
                }
                else
                {
                    if(dis[v][e.c] > w)
                    {
                        dis[v][e.c] = w;
                        pq.push(Node(v, e.c, w));
                    }

                    int64_t min_ = min((int64_t) e.w, mp[u][e.c] - e.w);
                    if(dis[v][0] > w + min_)
                    {
                        dis[v][0] = w + min_;
                        pq.push(Node(v, 0, w + min_));
                    }
                }
            }
        }
    }

    int modsub(int t1, int t2)
    {
        int64_t res = t1 - t2;
        if(res < 0) res += MOD;

        return res;
    }

    int modadd(int t1, int t2)
    {
        int64_t res = t1 + t2;
        if(res >= MOD) res -= MOD;

        return res;
    }

    int modmul(int t1, int t2)
    {
        int64_t res = 1LL * t1 * t2;
        return (res % MOD);
    }

    bool BIT(int mask, int j)
    {
        return (mask & MASK(j));
    }

    int64_t MASK(int j)
    {
        return (1LL << j);
    }

    int64_t Abs(int64_t t1)
    {
        if(t1 < 0) return -t1;
        return t1;
    }
};

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

//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
}

int main()
{
    __startup();
    int t = 1;
//    cin >> t;

    for(int i = 1; i <= t; i++)
    {
        Solution().solve();
    }

    return 0;
}

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