제출 #371599

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
371599		Dymo	Olympic Bus (JOI20_ho_t4)	C++14	21 / 100	35 ms	14060 KiB

ho_t4

#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")

#include<bits/stdc++.h>
using namespace std;

#define ll  long long
#define ull  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
//#define endl "\n"
const ll maxn =2e5+30;
const ll mod=1e9+7 ;
const ll base=1e18;


ll x[maxn];
ll y[maxn];
ll c[maxn];
ll d[maxn];
vector<ll> adj[maxn][2];
ll dp[maxn][6];
ll pre[maxn];
ll n, m ;
bool dd[maxn];

void dosth(ll p,ll type,ll ta,ll rc,ll t)
{
    priority_queue<pll,vector<pll>,greater<pll>> q;
    for (int i=1; i<=n; i++)
    {
        dp[i][type]=base;
    }
    dp[p][type]=0;
    q.push(make_pair(dp[p][type],p));
    while (!q.empty())
    {
        auto p=q.top();
        q.pop();
        ll u=p.ss;
        if (dp[u][type]!=p.ff)
            continue;
        for (auto to:adj[u][ta])
        {
            if (u==rc&&to==t)
                continue;
            ll nxt=x[to]+y[to]-u;
            if (dp[nxt][type]>dp[u][type]+c[to])
            {
                dp[nxt][type]=dp[u][type]+c[to];
                q.push(make_pair(dp[nxt][type],nxt));
                pre[nxt]=to;
            }
        }
    }

}
void dosth1()
{
    dosth(1,0,0,-1,-1);
    ll nw=n;
    while (nw!=1)
    {
       //  cout <<nw<<" "<<pre[nw]<<endl;
        dd[pre[nw]]=1;
        nw=x[pre[nw]]+y[pre[nw]]-nw;
    }
    dosth(1,1,1,-1,-1);
    dosth(n,2,0,-1,-1);
    dosth(n,3,1,-1,-1);
    ll ans=dp[n][0]+dp[n][1];
    for (int i=1; i<=m; i++)
    {
        if (dd[i])
        {
            ll h1=x[i];
            ll h2=y[i];
            adj[h2][0].pb(i);
            swap(x[i],y[i]);
            dosth(1,4,0,h1,i);
            ll h=dp[n][4]+d[i];
            dosth(n,4,0,h1,i);
            h+=dp[1][4];
            swap(x[i],y[i]);
            adj[h2][0].pop_back();


            ans=min(ans,h);
        }
        else
        {
            ans=min(ans,dp[n][0]+dp[x[i]][1]+dp[y[i]][2]+c[i]+d[i]);
            /*  if (min(dp[n][0],dp[y[i]][0]+dp[x[i]][3])+dp[x[i]][1]+dp[y[i]][2]+c[i]+d[i]==1)
              {
                  cout <<i<<endl;
              }*/
        }
    }
    if (ans>=base)
    {
        ans=-1;
    }
    cout <<ans;

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("graph.inp","r"))
    {
        freopen("graph.inp","r",stdin);
        freopen("graph.out","w",stdout);
    }

    cin>> n>> m;
    for (int i=1; i<=m; i++)
    {
        cin>>x[i]>> y[i]>>c[i]>> d[i ];
        adj[x[i]][0].pb(i);
        adj[y[i]][1].pb(i);
    }
    dosth(1,0,0,-1,-1);
    // cout <<dp[n][0]<<endl;
    if (dp[n][0]!=base)
    {
        dosth1();
    }
    else
    {
        dosth(n,0,0,-1,-1);
        if (dp[1][0]!=base)
        {
            for (int i=1; i<=n; i++)
            {
                adj[i][0].clear();
                adj[i][1].clear();
            }
            for (int i=1; i<=m; i++)
            {
                if (x[i]==n)
                    x[i]=1;
                else if (x[i]==1) x[i]=n;
                if (y[i]==n)
                    y[i]=1;
                else if (y[i]==1) y[i]=n;
               // cout <<x[i]<< " "<<y[i]<<endl;
                adj[x[i]][0].pb(i);
                adj[y[i]][1].pb(i);
            }
            dosth1();
        }
        else
        {
            dosth(1,0,0,-1,-1);
            dosth(1,1,1,-1,-1);
            dosth(n,2,0,-1,-1);
            dosth(n,3,1,-1,-1);
            ll ans=dp[n][0]+dp[n][1];
            for (int i=1; i<=m; i++)
            {
                ans=min(ans,dp[y[i]][0]+dp[x[i]][3]+dp[y[i]][2]+dp[x[i]][1]+d[i]+2*c[i]);
            }
            if (ans>=base)
            {
                ans=-1;
            }
            cout <<ans;
        }
    }




}

컴파일 시 표준 에러 (stderr) 메시지

ho_t4.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization("unroll-loops, no-stack-protector")
      | 
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  116 |         freopen("graph.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  117 |         freopen("graph.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 21 / 21
• Subtask 4: 0 / 63