제출 #692470

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
692470		abysmal	Robot (JOI21_ho_t4)	C++14	0 / 100	2125 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) 4 * 1e4;
const int64_t MOD = (int64_t) 1e9 + 7;
const int nbit = 30;
const int ndig = 10;
const int nchar = 26;
const int p1 = 31;
const int p2 = 53;
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;
    int p;
    int64_t w;

    Node(int u_, int c_, int p_, int64_t w_) : u(u_), c(c_), p(p_), 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<vector<int64_t> > > dis;
    vector<vector<Edge> > adj;
    Solution() {}

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

        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--;

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

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

        int64_t ans = INF;
        for(int i = 0; i <= m; i++)
        {
            ans = min(ans, dis[n - 1][i][0]);
            ans = min(ans, dis[n - 1][i][1]);
        }

        if(ans == INF) cout << "-1\n";
        else cout << ans << "\n";
    }

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

        vector<int64_t> cnt(m + 1, 0);
        while(!pq.empty())
        {
            Node x = pq.top();
            pq.pop();

            int u = x.u;
            int c = x.c;
            int b = 0;
            if(x.p != -1) b = 1;
            int64_t w = x.w;

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

                cnt[e.c] += e.w;
            }

            for(int i = 0; i < (int) adj[u].size(); i++)
            {
                Edge e = adj[u][i];
                int v = e.v;
                if(v == x.p) continue;

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

            for(int i = 0; i < (int) adj[u].size(); i++)
            {
                Edge e = adj[u][i];
                if(e.v == x.p && b != 0) continue;

                cnt[e.c] -= e.w;
            }
        }
    }

    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: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42