Submission #466513

#	Time	Username	Problem	Language	Result	Execution time	Memory
466513		Killer2501	Robot (JOI21_ho_t4)	C++14	100 / 100	1400 ms	109844 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define task "262144"
#define pll pair<ll, ll>
#define pi pair<ll, pll>
#define fi first
#define se second

using namespace std;
const ll mod = 1e15;
const ll N = 2e5+5;
const int base = 313;
ll n, m, t, k, T, ans, tong, a[N];
vector<ll> adj[N];
vector<ll> kq;
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}
map<ll, vector<pll>> mp[N];
map<ll, ll> dp[N], b[N];
void sol()
{
    cin >> n >> m;
    while(m -- > 0)
    {
        ll x, y, c, p;
        cin >> x >> y >> c >> p;
        b[x][c] += p;
        b[y][c] += p;
        mp[x][c].pb({p, y});
        mp[y][c].pb({p, x});
        dp[x][c] = mod;
        dp[y][c] = mod;
    }
    for(int i = 1; i <= n; i ++)dp[i][0] = mod;
    dp[1][0] = 0;
    priority_queue< pi, vector<pi>, greater<pi> > pq;
    pq.push({0, {1, 0}});
    while(!pq.empty())
    {
        pi u = pq.top();
        pq.pop();
        if(u.fi != dp[u.se.fi][u.se.se])continue;
        if(u.se.se)
        {
            for(pll v : mp[u.se.fi][u.se.se])
            {
                if(dp[v.se][0] > u.fi + b[u.se.fi][u.se.se] - v.fi)
                {
                   dp[v.se][0] = u.fi + b[u.se.fi][u.se.se] - v.fi;
                   pq.push({dp[v.se][0], {v.se, 0}});
                }
            }
        }
        else
        {
            for(auto vi : mp[u.se.fi])
            {
                for(pll v : vi.se)
                {
                    //cout << u.se.fi << " " << v.se <<" "<<v.fi << endl;
                    if(dp[v.se][vi.fi] > u.fi )
                    {
                       dp[v.se][vi.fi] = u.fi;
                       pq.push({dp[v.se][vi.fi], {v.se, vi.fi}});
                    }
                    if(dp[v.se][0] > u.fi + min(v.fi, b[u.se.fi][vi.fi] - v.fi))
                    {
                       dp[v.se][0] = u.fi + min(v.fi, b[u.se.fi][vi.fi] - v.fi);
                       pq.push({dp[v.se][0], {v.se, 0}});
                    }
                }
            }
        }
    }
    ans = dp[n][0];
    if(ans == mod)ans = -1;
    cout << ans;
}
int main()
{
    if(fopen(task".in", "r"))
    {
       freopen(task".in", "r", stdin);
       freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}
/*
4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1

*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:92:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |        freopen(task".in", "r", stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:93:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |        freopen(task".out", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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