Submission #637590

#	Time	Username	Problem	Language	Result	Execution time	Memory
637590		Huy	Robot (JOI21_ho_t4)	C++17	34 / 100	115 ms	59404 KiB

Main

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
/*#pragma GCC tarGet ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC tarGet("avx,avx2,fma")*/
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
const int N = 1e5;
const int maxN = 2e5 + 1;
const int mod = 1e9 + 7;
const int block_size = 700;
const ll infty = 1e18;

void InputFile()
{
    //freopen(".inp","r",stdin);
    //freopen(".out","w",stdout);
    freopen("test.out","r",stdin);
}

struct Tpq
{
    int ver,pre;
    int state;
    ll val;
};

struct functer
{
    bool operator()(Tpq a,Tpq b)
    {
        return a.val > b.val;
    }
};

int n,m;
int x[maxN],y[maxN],c[maxN],p[maxN];
vector<int> adj[maxN];
ll dp[1005][1005][2];
int cnt[maxN];
ll otc[maxN];

void Read()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> x[i] >> y[i] >> c[i] >> p[i];
        adj[x[i]].push_back(i);
        adj[y[i]].push_back(i);
    }
}

void Dijkstra()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            dp[i][j][0] = infty;
            dp[i][j][1] = infty;
        }
    }
    priority_queue<Tpq,vector<Tpq>,functer> q;
    dp[1][0][0] = 0;
    q.push({1,0,0,0});

    do
    {
        Tpq pick = q.top();
        q.pop();
        int u = pick.ver;
        int pre = pick.pre;
        int state = pick.state;
        if(dp[u][pre][state] != pick.val) continue;
        for(int i : adj[u])
        {
            int v = x[i] + y[i] - u;
            if(state && v == pre) continue;
            cnt[c[i]]++;
            otc[c[i]] += p[i];
        }
        for(int i : adj[u])
        {
            int v = x[i] + y[i] - u;
            if(state && v == pre)
            {
                //continue;
                if(dp[v][u][1] > dp[u][pre][state])
                {
                    dp[v][u][1] = dp[u][pre][state];
                    q.push({v,u,1,dp[v][u][1]});
                }
            }
            if(cnt[c[i]] > 1)
            {
                if(dp[v][u][1] > pick.val + p[i])
                {
                    dp[v][u][1] = dp[u][pre][state] + p[i];
                    q.push({v,u,1,dp[v][u][1]});
                }
                if(dp[v][u][0] > pick.val + otc[c[i]] - p[i])
                {
                    dp[v][u][0] = dp[u][pre][state] + otc[c[i]] - p[i];
                    q.push({v,u,0,dp[v][u][0]});
                }
            }
            else
            {
                if(dp[v][u][1] > pick.val + p[i])
                {
                    dp[v][u][1] = dp[u][pre][state] + p[i];
                    q.push({v,u,1,dp[v][u][1]});
                }
                if(dp[v][u][0] > pick.val)
                {
                    dp[v][u][0] = dp[u][pre][state];
                    q.push({v,u,0,dp[v][u][0]});
                }
            }
        }
        for(int i : adj[u])
        {
            cnt[c[i]] = 0;
            otc[c[i]] = 0;
        }
    }
    while(!q.empty());
}

void Solve()
{
    Dijkstra();
    ll res = infty;
    for(int i = 0; i <= n; i++)
    {
        res = min(res,dp[n][i][0]);
        res = min(res,dp[n][i][1]);
    }
    if(res >= infty) res = -1;
    cout << res;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve();
    int test;
    //cin >> test;
    test = 1;
    while(test--)
        //for(int prc = 1; prc <= test; prc++)
    {
        Read();
        Solve();
        //Debug();
    }
}

Compilation message (stderr)

Main.cpp: In function 'void InputFile()':
Main.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     freopen("test.out","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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