Submission #1086999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086999		khoile25108	Robot (JOI21_ho_t4)	C++14	100 / 100	735 ms	85312 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define FOD(i,a,b) for(int i = a; i >= b; i--)
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define lcm(a,b) (a*b)/__gcd(a,b)
#define ii pair<int,int>
#define iii pair<ll,pair<int,int>>
#define iv pair<pair<int,int>,pair<int,int>>

const int inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 105;

const int dx[] = {-1,0,1,0};
const int dy[] = {0,1,0,-1};
const int dxx[] = {-1,-1,0,1,1,1,0,-1};
const int dyy[] = {0,1,1,1,0,-1,-1,-1};

int n, m;
map<int,vector<iii>> g[N];
ll dp[N];
map<int,ll> dp2[N], sum[N];
// Giả sử ta đi trên đường u -> v -> k, dp2 là trường hợp mà thay vì đổi
// màu cạnh u -> v thì ta đổi màu các cạnh có cùng màu với cạnh u -> v
// nối với đỉnh v, khi đó, ta cũng xét cả th mà ta đổi cạnh kề v
// (chứa của u -> v) nhưng không đổi cạnh v -> k
// (màu v -> k == màu u -> v)

void dijk(int beg)
{
    priority_queue<iii,vector<iii>,greater<iii>> pq;
    pq.push({0,{1,0}});
    FOR(i,1,n) dp[i] = INF;
    dp[beg] = 0;
    while(!pq.empty())
    {
        int u = pq.top().se.fi;
        ll cost = pq.top().fi;
        int c = pq.top().se.se;
        pq.pop();
        if(c)
        {
            if(cost > dp2[u][c]) continue;
            for(auto H : g[u][c])
            {
                int v = H.fi;
                ll l = H.se.se;
                ll newcost = cost + sum[u][c] - l;
                if(newcost < dp[v])
                {
                    dp[v] = newcost;
                    pq.push({dp[v],{v,0}});
                }
            }
        }
        else
        {
            if(cost > dp[u]) continue;
            for(auto &graph : g[u])
            {
                for(auto H : graph.se)
                {
                    int v = H.fi;
                    int c = H.se.fi;
                    ll l = H.se.se;
                    ll case1 = cost + l; // đổi màu cạnh H
                    if(case1 < dp[v])
                    {
                        dp[v] = case1;
                        pq.push({dp[v],{v,0}});
                    }
                    ll case2 = cost + sum[u][c] - l;
                    // đổi màu các cạnh khác H cùng màu với H.
                    if(case2 < dp[v])
                    {
                        dp[v] = case2;
                        pq.push({dp[v],{v,0}});
                    }
                    ll case3 = cost; // đổi ở v.
                    if(!dp2[v].count(c) || case3 < dp2[v][c])
                    {
                        dp2[v][c] = case3;
                        pq.push({dp2[v][c],{v,c}});
                    }
                }
            }
        }
    }
}

void solve()
{
	dijk(1);
	cout << (dp[n] >= INF ? -1 : dp[n]);
}

void input()
{
	//freopen("TEST.INP", "r", stdin);
	//freopen("TEST.OUT", "w", stdout);
	cin >> n >> m;
	FOR(i,1,m)
	{
	    int u, v, c, d;
	    cin >> u >> v >> c >> d;
	    g[u][c].pb({v,{c,d}});
	    g[v][c].pb({u,{c,d}});
	    sum[u][c] += d;
	    sum[v][c] += d;
	}
}

signed main()
{
	faster
	input();
	solve();
}

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